Jack has several beautiful diamonds, each of them is unique thus precious. To keep them safe, he wants to divide and store them in different locations. First, he has bought some coffers. These boxes are identical except that their capacities (the number of the diamonds that a box can contain) may diverse. Before he puts his diamonds in, he wants to figure out how many different ways he can store these diamonds into the coffers. He recruits you, a young programmer from Zhejiang University, to give him the answer.

The input consists of several test cases. Each test case begins with a positive integer N, which indicates the number of the coffers Jack has bought. Then the following N integers are the capacities of each box. The total number of the diamonds Jack has equals to the sum of the capacities of all the coffers.

All the integers given are no greater than 12, you can be assured that a result always fits into a 32-bit integer.

For every test case, print out an integer representing the number of the different ways Jack can store his diamonds. Each integer is to be printed on a single line.