## KCARRY - Yet Another Electronic Device!!!

no tags

Fascinated as he is by the uncanny world of electronics, our friend MKS now decides to launch his own creation --> A N-Digit Carry Finder(an analogue of a N-Bit Binary Adder) which can be used to find the number of times we can have a non-zero carry while adding two numbers(A=AnAn-1...A2A1 and B=BnBn-1...B2B1) having exactly N digits.

It consists of 'N' Full Decimal Adders. The i-th Full Adder takes as input three digits Ai,Bi and Ci-1 and outputs a digit Ci(0 or 1), which is the carry generated on adding the digits Ai and Bi and Ci-1.(Ci=1 if Ai+Bi+Ci-1 >9, otherwise 0).

This Ci is now provided to the next (i+1-th) Full Adder in order to be added with the digits Ai+1 and Bi+1 and also to the accumulator which as the name suggests accumulates the sum of all Cj(1<=j<=i).

Note: C0=0 always and 0<=Ai,Bi<=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, A1=7,B1=4,C0=0 and A1+B1+C0=11. Therefore Carry C1=1.

In the 2nd Adder, A2=6,B2=3,C1=1 and A2+B2+C1=10. Therefore Carry C2=1.

In the 3rd Adder, A3=5,B3=7,C2=1 and A3+B3+C2=13. Therefore Carry C3=1.

In the 4th Adder, A4=7,B4=0,C3=1 and A4+B4+C3=8. Therefore Carry C4=0.

The Value in the Accumulator=C1+C2+C3+C4=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 ith line corresponding to the ith Test case .

Constraints:

1<=T<=500.

1<=N<=1000.

1<=K<=N.

## Example

4

1 1

2 1

2 2

3 3

### Sample Output

45

4500

2475

136125

Explanation
Example case 1.
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.

## Explanation

Example case 1.

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.

 < Previous 1 2 Next > Code7: 2016-07-21 15:31:28 AC in one go. Good DP question :) Last edit: 2016-07-21 15:31:56 Ankit Sultana: 2014-11-25 18:44:43 AC in first go!! chk: 2014-07-02 22:23:35 Niiice :D Vedang: 2014-05-23 16:09:12 people have solved the problem without global array interesting ... and still faster o_O (^-^): 2014-03-18 14:58:52 nyc problem enjoyed solving it :) utk1369: 2013-12-07 11:42:37 just to make thngs more clear: For N=3, all of the following types are counted: 000 005 056 345 and so on.... AAYUSH KUMAR: 2013-12-07 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].. EDIT: Corrected Now Last edit: 2013-12-07 11:43:43 (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-12-07 11:42:37 @Utkarsh Raj: Thanks :-) utk1369: 2013-12-07 11:42:37 @(Tjandra Satria Gunawan) Taken Care Of That. Time limit is now changed to 10s and All solutions have been rejudged. Last edit: 2013-08-08 22:17:10 (Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-12-07 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: 2013-08-08 06:41:56