Limits 1s, 512 MB

Everyone know about Mina & Raju. They are siblings as well as good friend. The friend-circle of Mina & Raju is huge also. They always play with their friends in every afternoon.

There are n boys & m girls in their friend-circle. They have a cultural program is their school coming in the next month. They are willing to perform a drama. They need to choose a group containing exactly t actors. Moreover, they need at least p boys & at least q girls in the group.

In how many ways they can choose a group following the rules mentioned above?

Input

The first line of input contains the number of test case tc (1 ≤ tc ≤ 100). Each test case of the input contains five integers n, m (1 ≤ n, m ≤ 100), p (1 ≤ p ≤ n), q (1 ≤ q ≤ m), t (p + q ≤ t ≤ n + m).

Output

For each test case, print a single integer — the required number of ways modulo 1000000007 (109 + 7).

Sample

InputOutput
2
3 3 3 3 6
3 3 2 2 5
1
6

Submit

Login to submit.

Statistics

77% Solution Ratio
PsychoKillerEarliest, Aug '18
Xiao_NaiFastest, 0.0s
MatrixLightest, 5.5 kB
steinumShortest, 467B
Toph uses cookies. By continuing you agree to our Cookie Policy.