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 P1, P2, P3, ..., PN (1 ≤ Pi ≤ 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 P1..N will be 1112222.
In addition, Raghav cannot eat more than Si sweets from box i in one step (s ≤ Si). Also, box i cannot be opened more than Bi times in total.
Can you help Raghav determine the total number of possible sequences P1..N satisfying the given constraints? Since this number can be large, compute it modulo 109 + 7.
- 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 space-separated integers p, q and N.
- The second line contains two space-separated integers B1 and B2.
- The third line contains two space-separated integers S1 and S2.
For each test case, print a single line containing one integer — the number of possible sequences modulo 109 + 7.
- 1 ≤ T ≤ 10
- 1 ≤ p, q ≤ 50
- 1 ≤ B1, B2, S1, S2 ≤ 200
- 1 ≤ N ≤ p+q
Subtask #1 (10 points): 1 ≤ N ≤ 15
Subtask #2 (20 points): 1 ≤ p, q ≤ 20
Subtask #3 (70 points): original constraints
Input: 2 2 2 4 2 2 1 1 10 10 10 10 10 10 10 Output: 2 1024
Example case 1: We have 2 sweets in box 1 and 2 sweets in box 2. All possible sequences P1..4 are: 1122, 2211, 1212, 2121, 1221 and 2112. Out of them, only 1212 and 2121 are valid, since S1 = S2 = 1.
Example case 2: All possible 210 sequences are valid.
|Tags||abx_2109, dynamic, ltime55, medium, programming|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.