Pro.ID10282 TitleMonkey Business Title链接http://10.20.2.8/oj/exercise/problem?problem_id=10282 AC0 Submit0 Ratio- 时间&空间限制描述The School of Food Sciences is running an experiment to study the effect of a healthy diet on the behaviour of monkeys. Each day the monkeys are separated into G groups. Each group has one or more monkeys and each group is given a single daily serving of fruits and vegetables according to the following rules: • each monkey receives no more than one vegetable, • each monkey receives the same number of fruits as the rest of monkeys in its group (otherwise they will go bananas), • only one type of fruit and only one type of vegetable may be made available to monkeys in the same group, • no two groups receive common fruit or vegetables, • the number of vegetables received by a group is strictly less than the number of its monkeys, and • each group receives no more than M fruits plus vegetables. The project has a daily budget to purchase B fruits and vegetables, which must be completely spent, and B ≤ 100*M. All fruits and vegetables have the same price. All purchased fruits and vegetables must be fed to the monkeys. For 2 groups, of 3 and 4 monkeys, there are 6 different ways to feed them on a budget of 5 with the condition that each group may have no more than 5 fruits plus vegetables. Your task, as the IT member, is to write a program to compute the number of different ways to feed the monkeys. 输入The input starts with an integer C, on a line by itself, that represents the number of test cases. 1 ≤ C≤ 100. Each test case consists of three integers B, G and M on a line by themselves. B is the budget of the day, G is the number of groups, and M is the maximum number of fruits plus vegetables that any group may receive. 1 ≤B≤ 10,000,000, and 1 ≤G, M≤ 100,000. 输出Description The School of Food Sciences is running an experiment to study the effect of a healthy diet on the behaviour of monkeys. Each day the monkeys are separated into G groups. Each group has one or more monkeys and each group is given a single daily serving of fruits and vegetables according to the following rules: • each monkey receives no more than one vegetable, • each monkey receives the same number of fruits as the rest of monkeys in its group (otherwise they will go bananas), • only one type of fruit and only one type of vegetable may be made available to monkeys in the same group, • no two groups receive common fruit or vegetables, • the number of vegetables received by a group is strictly less than the number of its monkeys, and • each group receives no more than M fruits plus vegetables. The project has a daily budget to purchase B fruits and vegetables, which must be completely spent, and B ≤ 100*M. All fruits and vegetables have the same price. All purchased fruits and vegetables must be fed to the monkeys. For 2 groups, of 3 and 4 monkeys, there are 6 different ways to feed them on a budget of 5 with the condition that each group may have no more than 5 fruits plus vegetables. Your task, as the IT member, is to write a program to compute the number of different ways to feed the monkeys. Input The input starts with an integer C, on a line by itself, that represents the number of test cases. 1 ≤ C≤ 100. Each test case consists of three integers B, G and M on a line by themselves. B is the budget of the day, G is the number of groups, and M is the maximum number of fruits plus vegetables that any group may receive. 1 ≤B≤ 10,000,000, and 1 ≤G, M≤ 100,000. Output For each test case, print the number of different ways to feed the monkeys as an integer, modulo the prime number 1000,000,007. Sample Input 3 Sample Output 6 Source 样例输入3 样例输出6 作者 |