Too Much Sweetness

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Raghav studies in NSIT and is bored of the regular hostel mess food. For a change he went to a sweet shop at City Centre near the college to have some sweets. There he found only two boxes containing sweets; box 1 contains p sweets and box 2 contains q sweets.
Initially, both boxes are closed. Raghav wants to eat exactly N sweets in total during the following process:
 Choose an index i (1 ≤ i ≤ 2) of one box and a number s (0 < s ≤ number of sweets in box i).
 Open box i, take out s sweets, eat them and then close box i.
 Write down number i exactly s times.
 If less than N sweets have been eaten in total, repeat from the first step.
The index i of the box chosen at each step should always be different from the index of the previously selected box. In the beginning, either box can be chosen.
At the end, Raghav will have written down a sequence P_{1}, P_{2}, P_{3}, ..., P_{N} (1 ≤ P_{i} ≤ 2 for each valid i) describing the boxes containing the sweets he ate, in the given order. For example, if he has to eat N = 7 sweets, so he opens box 1 and takes out 3 sweets and then opens box 2 and takes out 4 sweets, then the sequence P_{1..N} will be 1112222.
In addition, Raghav cannot eat more than S_{i} sweets from box i in one step (s ≤ S_{i}). Also, box i cannot be opened more than B_{i} times in total.
Can you help Raghav determine the total number of possible sequences P_{1..N} satisfying the given constraints? Since this number can be large, compute it modulo 10^{9} + 7.
Input
 The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each testcase contains three spaceseparated integers p, q and N.
 The second line contains two spaceseparated integers B_{1} and B_{2}.
 The third line contains two spaceseparated integers S_{1} and S_{2}.
Output
For each test case, print a single line containing one integer — the number of possible sequences modulo 10^{9} + 7.
Constraints
 1 ≤ T ≤ 10
 1 ≤ p, q ≤ 50
 1 ≤ B_{1}, B_{2}, S_{1}, S_{2} ≤ 200
 1 ≤ N ≤ p+q
Subtasks
Subtask #1 (10 points): 1 ≤ N ≤ 15
Subtask #2 (20 points): 1 ≤ p, q ≤ 20
Subtask #3 (70 points): original constraints
Example
Input: 2 2 2 4 2 2 1 1 10 10 10 10 10 10 10 Output: 2 1024
Explanation
Example case 1: We have 2 sweets in box 1 and 2 sweets in box 2. All possible sequences P_{1..4} are: 1122, 2211, 1212, 2121, 1221 and 2112. Out of them, only 1212 and 2121 are valid, since S_{1} = S_{2} = 1.
Example case 2: All possible 2^{10} sequences are valid.
Author:  abx_2109 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/ABX02 
Tags  abx_2109, dynamic, ltime55, medium, programming 
Date Added:  31102017 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 