PEG Judge - WC16 Finals - Rational Recipes

2016-17 Woburn Challenge Finals Round - Senior Division

Problem 2: Rational Recipes

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 ≤ N ≤ 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 ≤ F_i ≤ 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 × 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 × R₁ = F₁.

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) mod M = ((A mod M) + (B mod M)) mod M
(A × B) mod M = ((A mod M) × (B mod M)) mod M

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