Strategy for the World Cup

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Captain Dehatti from Bawanian village is making strategy to win the Fake Cricket World Cup organised in his village.
He want his team to score runs only in 4's and 6's because he believes that scoring any runs by running will make them tired.
He also wants that the team does not loose more than L wickets.
He now wonders in how many ways his team can score exactly R runs in B balls. Ofcourse, he assumes that the opponent bowling is awesome and will not concede any extra runs.
Formally, He wonders how many ways can his team score exactly R runs in B balls, given that each ball can result in 4, 6, 0 , or W(wicket wont add anything to score). Atmost L wicktes are allowed [i.e. Atmost L 'W' can be there in B balls ].
Note: His batting order is fixed i.e. After each wicket , next player to come is fixed.
Input
First line contains T, the number of test cases.
Each test case contains 3 space separated integers, R, B and L
Output
For each test cases output the number of ways modulo 1e9+7 (i.e. 1000000007)
Constraints
 1 ≤ T ≤ 25000
 0 ≤ R ≤ 10^{9}
 1 ≤ B ≤ 300
 0 ≤ L ≤ 9
Example
Input:
6 10 2 9 6 2 9 6 1 9 4 1 9 5 1 9 10 3 9
Output:
2 4 1 1 0 12
Explanation
Explanation for the sample input 1: All possible ways to face 2 deliveries: 00 04 06 0W W0 W4 W6 WW 40 44 46 4W 60 64 66 6W Only possible ways to win the match are 46 and 64. Hence answer is 2. You need to consider all sample space i.e. 4^B Note that the answer to R = 0 , B = 2 , W =1 is 3 [ 00 , 0W , W0 ]
Author:  devuy11 
Tester:  anudeep2011 
Editorial  http://discuss.codechef.com/problems/WORLDCUP 
Tags  combinatorics, cook55, devuy11, dynamicprogramming, maths, simple 
Date Added:  4022015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, PYP3, CLOJ, 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. 