KCARRY  Yet Another Electronic Device!!!
Fascinated as he is by the uncanny world of electronics, our friend MKS now decides to launch his own creation > A NDigit Carry Finder(an analogue of a NBit Binary Adder) which can be used to find the number of times we can have a nonzero carry while adding two numbers(A=A_{n}A_{n1}...A_{2}A_{1} and B=B_{n}B_{n1}...B_{2}B_{1}) having exactly N digits.
It consists of 'N' Full Decimal Adders. The ith Full Adder takes as input three digits A_{i},B_{i} and C_{i1} and outputs a digit C_{i}(0 or 1), which is the carry generated on adding the digits A_{i} and B_{i} and C_{i1}.(C_{i}=1 if A_{i}+B_{i}+C_{i1 }>9, otherwise 0).
This C_{i} is now provided to the next (i+1th) Full Adder in order to be added with the digits A_{i+1} and B_{i+1} and also to the accumulator which as the name suggests accumulates the sum of all C_{j}(1<=j<=i).
Note: C_{0}=0 always and 0<=A_{i},B_{i}<=9.
For Example: Adding two numbers , A=4567 and B=734(or B=0734), the addition proceeds as shown and the accumulator gets a final value of 3.
In the 1st Adder, A_{1}=7,B_{1}=4,C_{0}=0 and A_{1}+B_{1}+C_{0}=11. Therefore Carry C_{1}=1.
In the 2nd Adder, A_{2}=6,B_{2}=3,C_{1}=1 and A_{2}+B_{2}+C_{1}=10. Therefore Carry C_{2}=1.
In the 3rd Adder, A_{3}=5,B_{3}=7,C_{2}=1 and A_{3}+B_{3}+C_{2}=13. Therefore Carry C_{3}=1.
In the 4th Adder, A_{4}=7,B_{4}=0,C_{3}=1 and A_{4}+B_{4}+C_{3}=8. Therefore Carry C_{4}=0.
The Value in the Accumulator=C_{1}+C_{2}+C_{3}+C_{4}=3.
Your Task is to find the number of ways of getting a value K in the accumulator while adding two numbers containing at most N digits each. Note that we are adding the numbers in their base 10 representation. Since the total number of ways can be very large, print your answer modulo 1000000007(10^9 +7).
Input
The first line of input contains an integer T. Then T lines follow containing two space seperated integers N and K.
Output
Print the required answer modulo 1000000007(10^9 +7) in the i^{th} line corresponding to the i^{th} Test case .
Constraints:
1<=T<=500.
1<=N<=1000.
1<=K<=N.
Example
Sample Input
4
1 1
2 1
2 2
3 3
Sample Output
45
4500
2475
136125
Explanation
Example case 1.
The carry appears when adding
1 and 9, 2 and 9, 3 and 9 ... 9 and 9=9 cases.
2 and 8,3 and 8,4 and 8 ... 9 and 8=8 cases.
3 and 7,4 and 7,5 and 7 ... 9 and 7=7 cases.
.
.
.
9 and 1=1 case.
There are (9+8+7+6+5+4+3+2+1+0)=45 cases in total and in each case, the carry appears exactly once.
hide comments
Code7:
20160721 15:31:28
AC in one go. Good DP question :) Last edit: 20160721 15:31:56 

Ankit Sultana:
20141125 18:44:43
AC in first go!! 

chk:
20140702 22:23:35
Niiice :D 

Vedang:
20140523 16:09:12
people have solved the problem without global array interesting ... and still faster o_O 

(^^):
20140318 14:58:52
nyc problem enjoyed solving it :) 

utk1369:
20131207 11:42:37
just to make thngs more clear:


AAYUSH KUMAR:
20131207 11:42:37
gr88 problem.. enjoyed solving it.. [but shoudn't the statement be 2 nos A and B having "exactly" N digits bcoz the range of Ai & Bi are [0,9], i.e, 0 included]..


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20131207 11:42:37
@Utkarsh Raj: Thanks :) 

utk1369:
20131207 11:42:37
@(Tjandra Satria Gunawan) Taken Care Of That.


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20131207 11:42:37
Nice problem, but imho time limit should be increased. My python algo is TLE. whereas my C algo that use equivalent logic AC in first place (fastest). Last edit: 20130808 06:41:56 
Added by:  utk1369 
Date:  20130723 
Time limit:  1s4.824s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Based on a problem appeared in Codechef COOK36 