2016-17 Woburn Challenge Finals Round - Senior Division

The worst has come to pass, with the war between the monkeys and cows now officially in full swing. In fact, the first major battle has been scheduled for next week! As an experienced military leader, the Head Monkey is well aware of the importance of an often under-appreciated aspect of war – the nutritional well-being of the soldiers. She's taken it upon herself to personally prepare the upcoming battle's rations.

The Head Monkey has ~N~ ~(1 \le N \le 100)~ different types of fruit ingredients to work with, numbered from ~1~ to ~N~. Fruit type ~1~ corresponds to the monkeys' beloved bananas, of course, while the other fruit types are less tasty but have their own nutritional benefits. There are ~F_i~ ~(1 \le F_i \le 1\,000\,000\,000)~ fruits of the ~i~-th type available.

The Head Monkey intends to come up with a smoothie recipe, which will call for combining a certain set of fruits together to create a single smoothie. The recipe ~R~ will dictate that exactly ~R_i~ fruits of type ~i~ must go into the smoothie, where ~R_i~ is a strictly positive integer for each ~i~ between ~1~ and ~N~. It's unclear exactly what recipe she'll come up with, though – we can only hope that it will be edible, for the monkeys' sake.

It's also unclear how many monkeys will actually be participating in the upcoming battle, though the number of monkeys will surely be some positive integer. However, it's imperative that each of them receive a single smoothie, with all of the smoothies having been created using the same recipe as one another.

Of course, the number of available fruits is a serious limiting factor. If there are ~m~ monkeys, and some recipe ~R~ is chosen, then ~m \times R_i~ fruits of each type ~i~ will be required in total, and this quantity cannot exceed ~F_i~. However, there's an additional restriction – due to the high value placed on bananas, it's important that there be no leftover bananas, as they'd go to waste. Therefore, it must be the case that ~m \times R_1 = F_1~.

The Head Monkey has lots of great recipes in mind, but she's willing to accept that some of them might not work out in terms of producing a valid set of smoothies for ~1~ or more monkeys. That being said, she's wondering exactly how many different possible recipes she could validly choose. This quantity may be quite large, so she's only interested in its value when taken modulo ~10\,007~.

As a hint, the following properties of modular arithmetic may be useful:

• ~(A + B) \bmod M = ((A \bmod M) + (B \bmod M)) \bmod M~
• ~(A \times B) \bmod M = ((A \bmod M) \times (B \bmod M)) \bmod M~

In test cases worth ~2/12~ of the points, ~N \le 3~ and ~F_i \le 100~ for each ~i~.
In test cases worth another ~3/12~ of the points, ~F_i \le 100~ for each ~i~.
In test cases worth another ~2/12~ of the points, ~F_i \le 10\,000~ for each ~i~.

Input Specification

The first line of input consists of a single integer ~N~.
The second line of input consists of ~N~ space-separated integers ~F_1, \dots, F_N~.

Output Specification

Output one line consisting of a single integer – the number of different possible recipes which might be used (modulo ~10\,007~).

Sample Input

3
4 2 4

Sample Output

10

Sample Explanation

~3~ possible recipes are as follows:

• ~R = [4, 1, 3]~ (serving ~1~ monkey)
• ~R = [4, 2, 1]~ (serving ~1~ monkey)
• ~R = [2, 1, 2]~ (serving ~2~ monkeys)

There are ~7~ other possible recipes.