The statement of this problem is similar to that of
problem .
But here, the n weights do not need to be 2^{0}, 2^{1}, …, 2^{n−1}.

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^{6}.
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^{7}.

Public test cases

**Input**

1 20 3 1 2 4 3 6 10 4 8 1 2 3 4 5 6 7 8

**Output**

1 15 17 2130717

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++ Java