DCEPCA06 - Saving BOB

no tags 

Alice and Bob start playing a new game. Alice writes 2 numbers - N and K. She asks Bob to find an integer which is N digits long such that the absolute difference in the adjacent digits is greater than or equal to K. Bob realizes that a lot of integers satisfy this condition.  Can you help Bob to find the total number of N digit integers which satisfy the condition set by Alice?
Since the answer can be very large, print the answer modulus 1000000007.

Note :

The adjacent digits to a digit constitute both the left and right neighbor of the digit. Starting from the left, only the second digit is regarded as adjacent to the first digit and only the second last digit is regarded as adjacent to the last digit.

Constraints

T = 100
2 <= N <= 10^9
0 <= K <= 9

Input

First line contains T- the number of test cases. The next T lines contains two numbers N and K as given by Alice.

Output

Print T lines each containing the total number of integers of N digit mod 1000000007 which satisfy the condition set by Alice.

Example

Input:
2
2 9
2 8
 
Output: 1
4

hide comments
Vikas Kushwaha: 2013-09-22 09:22:23

Good one (Y) :)

Venkatesh Ganesan: 2013-09-20 08:57:02

Tried doing it in a "clever" way but in vain. Got it after doing it the "boring" way. :)

Still trying to find the error in my first solution. Willing to discuss it with anyone interested.

Last edit: 2013-09-20 08:59:46
Varun Nitish: 2013-09-18 01:37:12

AC in first attempt! :)

darryl: 2013-06-22 16:21:57

whew AC, i thought i'll get TLE

Aditya Pande: 2012-12-31 04:04:23

thank you, i had made a silly mistake...
got AC in 2nd best time.... :)

are the test cases random, I was expecting my 3rd attempt to be better than my second but strangely it is slower...

Last edit: 2012-12-31 09:02:53
(Tjandra Satria Gunawan)(曾毅昆): 2012-12-30 16:50:47

@Aditya Pande: did you check your program vs bruteforce program? or check for overflow?

Aditya Pande: 2012-12-30 14:48:02

i am getting WA and I don't know why....?
got my mistake and got AC

Last edit: 2012-12-31 09:02:35
(Tjandra Satria Gunawan)(曾毅昆): 2012-12-07 02:39:56

Got AC in 0.00s yeah! :-D seems that number of test cases is too small, only 100 cases....

Ehor Nechiporenko: 2012-12-06 16:17:34

Good problem Solved!)
Now I can optimize my solution as well))


Added by:dce coders
Date:2012-12-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA
Resource:Own Problem