Permutations and Combinations
All submissions for this problem are available.
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 less 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.
The input contains of several test cases. Each test case contains N and K separated by a space respectively. The last line "0 0" signifies end of input and no output is to be printed for it.
One line containing the answer for each test case
T(1 <= T <= 1000) - Number of test cases.
2 <= N <= 10^9
0 <= K <= 9
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, GO, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.