Given an array p1,p2,...,pn which is a permutation of 1 to n, one can ask a problem of whether pi is the largest number among p1,p2,...,pi. While Zghh was doing this problem he thought that solving such a simple problem was descending his intellengence. Therefore he casually wrote down a part of the answer. What he wrote was another array f1,f2,...,fn where fi = 1 if pi is the largest number among p1,p2,...,pi while fi = -1 if pi is not the largest number among p1,p2,...,pi and fi = 0 means Zghh left it blank deliberately. After having written down those numbers, Zghh thought out another much more interesting problem. Let LIS(p) be the length of the longest increasing subsequence of p. Zghh wondered given the value f1,f2,...,fn, what is the expectation of LIS(p). Of course he figured it out after the second he thought of the problem but he was too lazy and wanted you to write down the answer for him.

The first line contains an integer n(1<=n<20).

The second line contains n integers f1 f2 ... fn.

The data is made such that at least one permutation of 1 to n suit the array f.

Suppose your answer is p/q, output two positive integer p q in a line. Make sure p and q are coprime numbers.

3
0 0 0

2 1

all 6 permutations of 123 satisfied the given f.

LIS(123)=3, LIS(132)=2, LIS(213)=2, LIS(231)=2, LIS(312)=2, LIS(321)=1,

(3+2+2+2+2+1)/6 = 12/6 =  2/1

3
1 -1 0

5 3

3 permutations of 123 satisfied the given f.

LIS(213)=2, LIS(312)=2, LIS(321)=1,

(2+2+1)/3 = 5/3