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 different types of fruit ingredients to work with, numbered from to . Fruit type corresponds to the monkeys' beloved bananas, of course, while the other fruit types are less tasty but have their own nutritional benefits. There are fruits of the -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 will dictate that exactly fruits of type must go into the smoothie, where is a strictly positive integer for each between and . 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 monkeys, and some recipe is chosen, then fruits of each type will be required in total, and this quantity cannot exceed . 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 .
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 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 .
As a hint, the following properties of modular arithmetic may be useful:
In test cases worth of the points, and for each .
In test cases worth another of the points, for each .
In test cases worth another of the points, for each .
Input Specification
The first line of input consists of a single integer .
The second line of input consists of space-separated integers
.
Output Specification
Output one line consisting of a single integer – the number of different possible recipes which might be used (modulo ).
Sample Input
3
4 2 4
Sample Output
10
Sample Explanation
possible recipes are as follows:
- (serving monkey)
- (serving monkey)
- (serving monkeys)
There are other possible recipes.
Comments