We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Mathematics
- Combinatorics
- Permutation Problem
Permutation Problem
Permutation Problem
How many n-digit numbers (without leading zeros) are there such that no digit occurs more than k times?
As the count of such n-digit numbers can be very large, print the answer mod (109+7)
Input Format
The first line contains an integer, T , the number of test cases. This is followed by T lines each containing 2 space separated integers, n and k
Constraints
T ≤ 100000
1 ≤ n ≤ 1000
1 ≤ k ≤ 109
Sample Input
2
2 3
2 1
Sample Output
90
81
Explanation
Case 1: A number can appear three times. So we have 9 (all except 0) numbers for first digit and 10 numbers for the second digit.
Case 2: A number can appear only once. So we have 9 choices for the first digit and 9(all except the first one) for the second digit.