DCEPCA06  Saving BOB
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:
20130922 09:22:23
Good one (Y) :) 

Venkatesh Ganesan:
20130920 08:57:02
Tried doing it in a "clever" way but in vain. Got it after doing it the "boring" way. :)


Varun Nitish:
20130918 01:37:12
AC in first attempt! :) 

darryl:
20130622 16:21:57
whew AC, i thought i'll get TLE 

Aditya Pande:
20121231 04:04:23
thank you, i had made a silly mistake...


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121230 16:50:47
@Aditya Pande: did you check your program vs bruteforce program? or check for overflow? 

Aditya Pande:
20121230 14:48:02
i am getting WA and I don't know why....?


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20121207 02:39:56
Got AC in 0.00s yeah! :D seems that number of test cases is too small, only 100 cases.... 

Ehor Nechiporenko:
20121206 16:17:34
Good problem Solved!)

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