Krusty's Burger

Time limit1sMemory limit256 MB

Summary

Count burger combinations of size, bun, cheeses, toppings and sauces whose size plus extra-item cost is at most B.

Level: Medium5 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Problem

Your friend Krusty runs a build-your-own-burger restaurant. A burger is assembled in five steps.

Pick a burger size.
Pick one bun out of $N_b$ different buns.
Pick no cheese, or one cheese out of $N_c$ different cheeses.
Pick up to 3 toppings out of $N_t$ different toppings.
Pick no sauce, or one sauce out of $N_s$ different sauces.

A burger costs $1 per 50 grams, and the size can be any positive multiple of 50 grams. Every item beyond the allowances in steps 3 to 5 costs $1, so a second cheese, a second sauce, and each topping after the third one add $1 each.

For example, a 100 gram burger on bun number 1 with 2 different cheeses, 5 toppings and no sauce costs $5: $2 for the size, $1 for the extra cheese, and $2 for the two extra toppings.

Given a budget $B$ , count the burgers that can be built for at most $B$ . Two burgers are different if one of them contains a burger size, a bun, a cheese, a topping, or a sauce that the other one does not contain.

Input

The first line contains one integer $T$ , the number of test cases. Each of the next $T$ lines contains five integers $B$ , $N_b$ , $N_c$ , $N_t$ , $N_s$ separated by spaces.

$1 \le T \le 20$
$1 \le B, N_b, N_c, N_s \le 1000$
$3 \le N_t \le 1000$

Output

For each test case, print the number of different burgers that fit in the budget on its own line. The count can be very large, so print it modulo 1,000,000,007.

Examples2

Example 1

Input

Expected output

632
32
299700

Example 2
Input
```
1
1 1 1 3 1
```
Expected output
```
32
```