28342번 - N-beat 다국어

문제

N-beat is a popular rhythm arcade game, in which you push buttons arranged in a $x \times y$ grid. The buttons light up when you have to push them; you have to push them with precise timing to get scores.

One game of N-beat consists of one or more screens. A screen is a configuration of lit buttons which you have to push.

For example, the picture above shows 4ドル$ successive screens for a N-beat machine with 4ドル \times 4$ grid. Here, boxes with the target mark are the lit buttons you have to press.

A sequence of screens in a game is called a transcription.

Now, Jaeha Koo, a genius composer, just made a new song for N-beat. You’re going to make transcription for this song.

There are $B$ beats in this song, so this transcription will consist of $B$ screens. Therefore, without any restriction, there are a total of $(2^{xy})^B$ possible transcriptions.

But transcriptions differ in difficulty. Generally, you can push one button with one finger, so it’s harder when a single screen has more lit buttons. Especially, if a screen has more than 10ドル$ lit buttons, it’s very difficult to push them successfully. Also, adjacent screens having a lot of lit buttons can also can make the game difficult. For example, two successive screens with 7ドル$ and 6ドル$ lit buttons each might be more difficult than two screens with 2ドル$ and 8ドル$ lit buttons each.

As a generous transcriptor, you decided to limit the number of lit buttons. The limit is given as three nonnegative integers: $p_1,ドル $p_2,ドル and $p_3$. $p_1$ is the maximum number of lit buttons you can have in any one screen. $p_2$ is the maximum number of lit buttons you can have in any two consecutive screens. Also, as you guessed, $p_3$ is the maximum number of lit buttons you can have in any three consecutive screens. In the picture above, 4ドル$ screens each have 4ドル,ドル 8ドル,ドル 6ドル,ドル 8ドル$ of turned-on buttons, so this transcription will only be valid if $p_1 ≥ 8,ドル $p_2 ≥ 14,ドル and $p_3 ≥ 22$.

Your task is to calculate the number of possible transcriptions given $x,ドル $y,ドル $B,ドル $p_1,ドル $p_2$ and $p_3$. As the result can be quite huge, just calculate the answer mod 10ドル^9 + 7$.

입력

The input consists of $T$ test cases. The first line of the input contains $T$.

Each test case starts with 6ドル$ integers $x,ドル $y$ (1ドル ≤ x, y ≤ 1000$), $B$ (1ドル ≤ B ≤ 10^9$), $p_1$ (0ドル ≤ p_1 ≤ 10$), $p_2$ (0ドル ≤ p_2 ≤ 20$), $p_3$ (0ドル ≤ p_3 ≤ 30$) separated by a whitespace.

출력

For each test case, print the number of possible transcriptions mod 10ドル^9 + 7,ドル in a single line.

제한

힌트