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:
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. :)
|
|
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...
|
|
(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....?
|
|
(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!)
|
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 |