You are given a sequence of N integers as A₁, A₂, ... , A_N. Let B be a sub-sequences of A, of maximum possible length (say k), such that each of them satisfies following conditions:

• |B_i| > |B_i-1|
  

• B_i * B_i-1 < 0
  

for all i = 2, 3, ... k

Find number of distinct sub-sequences of length k that satisfy above conditions. Two sub-sequences are distinct if they are made up using different set of indices of sequence A.

CONSTRAINTS

1 ≤ N ≤ 10⁵
-10⁵ ≤ A_i ≤ 10⁵ for all i = 1, 2, 3, ... N
A_i != 0 for all i = 1, 2, 3, ... N

INPUT

First line contains one integer N, denoting the size of input array. Next line contains N space separated integers, denoting the array A.

OUTPUT

Print two space separated integers, first one k, denoting the maximum possible size of such a sub-sequence and second integer d, the number of all such sub-sequences. Since d can be large, print it modulo 10⁹+7.