Balance (2) P17598

The statement of this problem is similar to that of problem P92795: “Balance (1)”. But here, the n weights do not need to be 2⁰, 2¹, …, 2ⁿ⁻¹.

I.e., the problem is: Given n weights, we have to place all the weights on a balance, 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.

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 balance. This number will never be larger than 10⁷.