beecrowd | 1333

Candy’s Candy

By Pablo Ariel Heiber Argentina

Timelimit: 1

Candy has a stock of candy of F different flavors. She is going to make several packs of candy to sell them. Each pack must be either a flavored pack, containing candy of a single flavor, or a variety pack, containing candy of every flavor. Candy wants to make a nice packing with her candy. She decided that a nice packing must honor the following conditions:

Candy is wondering how many different nice packings of candy she could make. Two nice packings of candy are considered different if and only if they differ in the number of flavored packs, or in the number of variety packs, or in the number of pieces of candy per pack. Since Candy will sell her candy during the closing ceremony of this contest, you are urged to answer her question as soon as you can.

Input

Each test case is described using two lines. The first line contains an integer F indicating the number of flavors (2 ≤ F ≤ 105). The second line contains F integers Ci, indicating the number of pieces of candy of each flavor (1 ≤ Ci ≤ 109 for 1 ≤ iF).

The last test case is followed by a line containing one zero.

Output

For each test case output a line with an integer representing the number of different nice packings of candy, according to the rules given above.

Sample Input Sample Output

3
15 33 21
2
1 1
2
2 2
2
3 3
3
1000000000 1000000000 1000000000
0

4
0
0
1
832519396