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 (10^{9}+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 ≤ 10^{9}

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.

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Starter code:

Solutions:
from math import factorial

def choose(n, k):
	total = factorial(n) // factorial(k)
	total = total // factorial(n - k)
	return int(total)

def incl(n, k, i):
	total = 1
	for j in range(0, i):
		total = (10 - j) * total * choose(n - j * k, k)
	return total

def excl(n, k, i):
	total = choose(n - 1, k - 1)
	for j in range(1, i):
		total = (10 - j - 1) * total * choose(n - j * k, k)
	return total
T = int(input())
for k in range(T):
	pair = str(input()).split(' ')
	N = int(pair[0])
	K = int(pair[1]) + 1
	total = 10 ** N - 10 ** (N - 1)
	i = 1
	while N >= i * K:
		if i % 2 == 1:
			total = total - incl(N, K, i) + excl(N, K, i)
		else:
			total = total + incl(N, K, i) - excl(N, K, i)
		i = i + 1
	total = total % (10 ** 9 + 7)
	print(total)


def f(n, k):
	if k <= 0 or n > 10 * k:
		return 0
	if k >= n:
		res = 9
		while n > 1:
			res = res * 10 % 1000000007
			n = n - 1
		return res
	elif k == 1:
		res = 9
		for i in range(10 - n + 1, 10):
			res = res * i
		return res
	return 9 * f(n - 1, k) % 1000000007 + f(n - 1, k - 1) % 1000000007
T = int(input())
for j in range(0, T):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	print(str(f(n, k)))


import math

def combination(n, r):
	answer = 1
	r = min(r, n - r)
	answer = 1
	for i in range(1, r + 1):
		answer *= (n - i + 1) / i
	return answer
test = int(input())
for _ in range(test):
	stri = input().split()
	(n, k) = (int(stri[0]), int(stri[1]))
	answer = 9 * 10 ** (n - 1)
	if k >= n:
		answer = answer % (10 ** 9 + 7)
		print(answer)
	else:
		for i in range(k + 1, n + 1):
			answer -= 9 ** (n - i + 1) * int(combination(n, i))
		answer = answer % (10 ** 9 + 7)
		print(answer)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = 9
	t = 10
	for i in range(1, n):
		if i + 1 > k:
			t -= 1
		s *= t
	print(s % (10 ** 9 + 7))


num_cases = int(input())
div = 10 ** 9 + 7
for _ in range(num_cases):
	(n, k) = tuple([int(x) for x in input().split()])
	ans = 9
	for i in range(1, n):
		num_comb = 10
		if k < n:
			num_comb -= k * i
		ans *= num_comb
	print(ans % div)


def solve(N, K):
	D = [1, 9]
	for n in range(1, N):
		if n < K:
			D.append(D[-1] * 10)
		else:
			D.append(D[-1] * 10 - D[n - K] * 9)
	return D[-1] % (10 ** 9 + 7)
T = int(input())
for t0 in range(T):
	(N, K) = (int(a) for a in input().split())
	print(solve(N, K))


import math
for _ in range(0, int(input())):
	(n, k) = map(int, input().split())
	if k > n:
		k = n
	if 9 + 10 * (k - 1) < n:
		print(0)
		continue
	ans = 9 * 10 ** (min(k, n) - 1)
	mult = 10
	digitsAchieved = min(k, n)
	while digitsAchieved < n:
		mult = mult - 1
		ans = ans * mult ** min(k, n - digitsAchieved)
		digitsAchieved = digitsAchieved + min(k, n - digitsAchieved)
	print(ans % 1000000007)


import sys
import math
t = int(input().strip())
if t <= 100000 and t >= 0:
	c = []
	for i in range(t):
		(n, k) = input().strip().split(' ')
		(n, k) = (int(n), int(k))
		c.append((n, k))
	for (n, m) in c:
		if n <= 1000 and n >= 1 and (m >= 1) and (k <= pow(10, 9)):
			s = 0
			if m >= n:
				s = pow(10, n - 1) * 9
				s = s % (pow(10, 9) + 7)
			else:
				s = int(9 * pow(10, k - 1)) % (pow(10, 9) + 7)
				s = s * int(math.factorial(9) / math.factorial(max(0, 9 - n + k)))
				s = s % (pow(10, 9) + 7)
			print(s)


t = int(input())
m = 1000000007
while t:
	t -= 1
	(n, k) = map(int, input().split())
	if 10 * k < n:
		print(0)
	elif k >= n:
		print(9 * pow(10, n - 1, m) % m)
	else:
		r = 1
		s = 1
		s = 9 * pow(10, k - 1, m) % m
		n -= k
		for i in range(0, n // k):
			s = s * pow(10 - r, k, m) % m
			r -= 1
		if n % k != 0:
			s = s * pow(10 - r, n - k * (r - 1), m) % m
		print(s)


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L.append(0)
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total % m

def nchoosek(n, k):
	a = 1
	if n < 0 or k < 0 or n < k:
		return 0
	for i in range(0, k):
		a *= n - i
	for j in range(1, k + 1):
		a //= j
	return a

def build_nchoosek_array(n, modulus):
	L = [[1]]
	current = []
	for i in range(1, n + 1):
		current.append(L[i - 1][0])
		for j in range(1, i):
			current.append((L[i - 1][j] + L[i - 1][j - 1]) % modulus)
		current.append(L[i - 1][i - 1])
		L.append(current)
		current = []
	return L

def n_digit_numbers_k_rep(N, K, modulus):
	total = 0
	for r in range(K + 1, N + 1):
		total += 9 * nchoosek(N - 1, r - 1) * pow_mod(9, N - r, modulus) + 8 * 10 * nchoosek(N - 1, r) * pow_mod(9, N - r - 1, modulus)
		total %= modulus
	return (9 * pow_mod(10, N - 1, modulus) - total) % modulus
q = int(input())
m = pow(10, 9) + 7
for _ in range(0, q):
	(N, K) = [int(a) for a in input().split()]
	print(n_digit_numbers_k_rep(N, K, m))


num_tests = int(input())
for _ in range(num_tests):
	options = 9
	(N, K) = [int(i) for i in input().split()]
	for i in range(1, N):
		handicap = i // K
		options = options * (10 - handicap) % 1000000007
	print(options)


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L.append(0)
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total % m

def nchoosek(n, k):
	a = 1
	if n < 0 or k < 0 or n < k:
		return 0
	for i in range(0, k):
		a *= n - i
	for j in range(1, k + 1):
		a //= j
	return a

def build_nchoosek_array(n, modulus):
	L = [[1]]
	current = []
	for i in range(1, n + 1):
		current.append(L[i - 1][0])
		for j in range(1, i):
			current.append((L[i - 1][j] + L[i - 1][j - 1]) % modulus)
		current.append(L[i - 1][i - 1])
		L.append(current)
		current = []
	return L

def n_digit_numbers_k_rep(N, K, modulus):
	total = 0
	for r in range(K + 1, N + 1):
		total += 9 * nchoosek(N - 1, r - 1) * pow_mod(9, N - r, modulus) + 8 * 10 * nchoosek(N - 1, r) * pow_mod(9, N - r - 1, modulus)
		total %= modulus
	return (9 * pow_mod(10, N - 1, modulus) - total) % modulus
q = int(input())
m = pow(10, 9) + 7
for _ in range(0, q):
	(N, K) = [int(a) for a in input().split()]
	print(n_digit_numbers_k_rep(N, K, m))