11178번 - Krusty’s Burger 다국어

Your friend Krusty is running a “build your own burger”- restaurant. You follow these steps to build a burger:

1. Pick a burger size.
2. Pick a bun from N_b different buns.
3. Pick no cheese or a cheese from N_c different cheeses.
4. Pick up to 3 toppings from N_t different toppings.
5. Pick no sauce or a sauce from N_s different sauces.

Burgers cost \$1 per 50 grams and you can choose any burger size, as long as you stick to a nonzero positive multiple of 50 grams. You can add additional cheeses, sauces or toppings for \$1 per extra item.

For example, a burger with 100 grams, on bun number 1, with 2 different cheeses, 5 toppings, and no sauce, would cost \$5: \$2 for the burger, \$1 for the extra cheese and \$2 for the extra toppings.

Realizing that you have a huge array of options, your friend would like you to find out how many different burgers you can build without exceeding a given budget, B. Two burgers are different if one contains a burger size, bun, cheese, topping or sauce that the other one doesn’t contain.

The first line of the input consists of a single integer, T, the number of test cases. Each of the following T cases consists of the 5 numbers B, N_b, N_c, N_t, N_s separated by spaces.

• 1 ≤ T ≤ 20
• 1 ≤ B, N_b, N_c, N_s ≤ 1000
• 3 ≤ N_t ≤ 1000

For each test case, output the number of different burgers that can be built within the budget. This number can be very large, so the answer should be given modulo 1,000,000,007