Balance (2) P17598

The statement of this problem is similar to that of problem problem://problemsjutge.org:problems/upc/2011-final/8-balance-1.pbm. 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 \le n \le 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$.