Hurray.. you've won the grand prize in Felicity 2010!!
Now its time to claim your prize through lucky draw, the procedure of which is given below.
You will take out coupons from the coupon box. Each coupon has a unique prize mentioned on it.
You can get a maximum of N prizes. Once you take a coupon out in a step, you will put it back in the box before continuing next step.
The coupon box contains three types of coupons. Your prize depends on the basis of the coupon you took out.
If the coupon you took out turns out to be of type A, you collect the prize mentioned on it. If this is your Nth prize, you have to stop. Otherwise, you take more coupons and continue the process.
If it turns out to be of type B, you can collect the prize mentioned on the coupon any number of times (but at least one), provided that the total number of prizes dont exceed N. After you have taken, you have to stop, you can't take any more coupons.
If it turns out to be of type C, you collect the prize mentioned on the coupon, but you cant collect anymore coupons and have to stop.
Find the number of ways of getting prizes (modulo 10000).
2 ways are considered different if the ith prize you get are different for some i.
First line contains the number of test cases
Each test case consists of 4 integers : Na, Nb, Nc and N.
Na, Nb and Nc corresond to the number of coupons of each type in the box.
Number of test cases <= 10
Na,Nb,Nc < 1000
N<=1010
For each test case, print a single line which contains the number of different ways possible modulo 10000
1 1 1 2 2
8
Migrated from old NTUJ.
CodeCraft 2010
| No. | Testdata Range | Score |
|---|