Balanced scales V45017

Given n weights, we have to place all of them on a scale, one after another, in such a way that the right pan is never heavier than the left pan. Please compute the number of ways of doing this.

For example, for n=3 and weights {1,2,4}, possible solutions are

where 1ℓ means that the weight 1 is placed on the left pan and 2r means that the weight 2 is placed on the right pan. We remark, as it can be seen in the example, that the order in which we place the weights does matter. Hence, (2ℓ,4ℓ,1r) and (2ℓ,1r,4ℓ) are different solutions.

Input

Input consists of several cases, each with the number of weights n followed by n different weights, all between 1 and 10⁶. Assume 1 ≤ n ≤ 8.

Output

For every case, print the number of correct ways of placing the weights on the scale. This number will never be larger than 10⁷.