EIU Programming Practices and Exams

There is a row of precious timber forests of n trees numbered from 1 to n and each tree has a monetary value of k. Leo is about to get married, so he wants to choose some cut trees to sell for money. But he is a person who loves nature very much, he does not want to destroy all the forests, so he complies with 2 conditions:

• Never cut down two consecutive trees
• There are some trees of the rare species with the value k < 0, if the Beo is cut down, he will be fined a mount of money which is equal the absolute value of that tree.

Calculate the maximum amount of money Beo can earn and how many ways he can earn that amount of money.

Input

The first line contains a single integer n (1≤ n ≤ 10⁵)

The next line contains n integers ki (1≤ i ≤ n , |k| ≤ 10⁹) -value of each tree.

Output

Output in a row the maximum amount Beo can get, and the number of ways Bell can choose to cut down the tree. The number of ways to cut a tree can be very large, the printed result is the remainder when divided by 10⁹+7.

Example

Input:
6
3 1 3 3 2 2

Output:
8 3