To enforce communication, n cities decided to exchange citizens for some time. There are ai (1<=i<=n, ai>0) families in the ith city join in this activity, which goes like this: each family will send one child to live with another family for one week, and obviously will accommodate one. However the children will not be sent to the families in their own cities. Then how many ways of arrangement can be made?
Input
There are several test cases. Each test case contains two lines.
The first line there is an integer n, the number of cities.
The second line there are n integers indicate the number of participants in each city.
The totle number of participants will not exceed 15.
Output:
For each test case, print in one line the number of permutation.
Sample Input:
1
15
3
2 2 3
Sample Output:
0
288
