All submissions for this problem are available.
One day there was a naughty kid in the circus. The kid challenged the head clown in a very strange manner. The kid gave him a problem which he knew that the clown wont be able to solve as he was the dumbest person on earth. Now, you being the head assistant have been asked by the circusmaster to help the clown save his face.
The question goes like this:
How many strings are possible such that none of its substrings is a permutation of 0,1,....,K. The condition is that all the characters in the string are numeric and between 0 to K (inclusive) and the length of the string is N.
Input starts with an integer T (T ≤ 200), denoting the number of test cases.
Each case contains two integers, N and K. N (1 ≤ N ≤ 1018) represents the length of the strings, and K (1 ≤ K ≤ 9) represents the biggest digit in the string.
For each case, output the number of such strings. As the answer can be very large, output answer mod 109+7.
2 1 1 2 1
For the first test case the strings are 0 and 1.
For the second test case the strings are 00, 11. 01 and 10 are not possible.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, PYTH, PYTH 3.6, CS2, RUBY, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.