VK gave a problem to Chef, but Chef is too lazy, so he asked you to solve the problem for him. The statement of the problem follows.
Consider an integer with $N$ digits (in decimal notation, without leading zeroes) $D_1, D_2, D_3, \dots, D_N$. Here, $D_1$ is the most significant digit and $D_N$ the least significant. The weight of this integer is defined as ∑i=2N(Di−Di−1).∑i=2N(Di−Di−1).\sum_{i=2}^N (D_i - D_{i-1})\,.
You are given integers $N$ and $W$. Find the number of positive integers with $N$ digits (without leading zeroes) and weight equal to $W$. Compute this number modulo $10^9+7$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $N$ and $W$ denoting the number of digits and the required weight.

-----Output-----
For each test case, print a single line containing one integer — the number of $N$-digit positive integers with weight $W$, modulo $10^9+7$.

-----Constraints-----
- $1 \le T \le 10^5$
- $2 \le N \le 10^{18}$
- $|W| \le 300$

-----Subtasks-----
Subtask #1 (20 points):
- $1 \le T \le 10^3$
- $2 \le N \le 10^3$
Subtask #2 (80 points): original constraints

-----Example Input-----

1
2 3

-----Example Output-----

6

-----Explanation-----
Example case 1: Remember that the digits are arranged from most significant to least significant as $D_1, D_2$. The two-digit integers with weight $3$ are $14, 25, 36, 47, 58, 69$. For example, the weight of $14$ is $D_2-D_1 = 4-1 = 3$. We can see that there are no other possible numbers.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics


Solutions:
t = int(input())
for _ in range(t):
	(n, w) = map(int, input().split())
	count = 0
	mod = 10 ** 9 + 7
	if w >= 0:
		count = 9 - abs(w)
	else:
		count = 10 - abs(w)
	if w >= -9 and w <= 8:
		print(pow(10, n - 2, mod) * count % mod)
	else:
		print(0)


DIVISOR = 10 ** 9 + 7

def main():
	T = int(input())
	for t in range(T):
		(N, W) = map(int, input().split(' '))
		if W > 8 or W < -9:
			print(0)
			continue
		if W >= 0:
			first_digits = 9 - W
		elif W < 0:
			first_digits = 10 + W
		print(first_digits * pow(10, N - 2, DIVISOR) % DIVISOR)
main()


def li():
	return list(map(int, input().split()))

def si():
	return input().split()

def ii():
	return int(input())

def ip():
	return input()

def pow(a, b):
	ans = 1
	inf = 1000000007
	while b > 0:
		if b & 1:
			ans = ans * a % inf
		a = a * a % inf
		b >>= 1
	return ans
for tastcas in range(int(input())):
	(n, w) = li()
	inf = 1000000007
	if w >= -9 and w <= 8:
		c = 0
		for d1 in range(1, 10):
			for d2 in range(0, 10):
				if d2 - d1 == w:
					c += 1
		print(c * pow(10, n - 2) % inf)
	else:
		print(0)


t = int(input())
for j in range(t):
	n = 0
	(a, b) = map(int, input().split())
	for i in range(0, 10):
		for k in range(1, 10):
			if i - k == b:
				n += 1
	k = pow(10, a - 2, 10 ** 9 + 7)
	k = k * n % (10 ** 9 + 7)
	print(k)


t = int(input())
for case in range(t):
	(n, w) = map(int, input().split())
	if abs(w) > 9:
		print(0)
		continue
	c = pow(10, n - 2, 1000000007)
	if w >= 0:
		c *= 9 - w
	else:
		c *= 10 + w
	print(c % 1000000007)


mn = 1000000007
for _ in range(int(input())):
	(n, w) = [int(x) for x in input().split()]
	if w <= 9 and w >= -9:
		if w < 0:
			w = w * -1
			a = (10 - w) * pow(10, n - 2, mn) % mn
			print(a)
		else:
			a = (9 - w) * pow(10, n - 2, mn) % mn
			print(a)
	else:
		print(0)


t = int(input())
while t:
	(n, w) = [int(n) for n in input().split()]
	f = int(1000000000.0 + 7)
	count = pow(10, n - 2, f)
	if w > 8 or w < -9:
		print(0)
	elif w >= 0:
		p = count * (9 - w)
		print(p % f)
	else:
		w = -w
		p = count * (9 - w + 1)
		print(p % f)
	t = t - 1


T = int(input())

def power(x, s, p):
	result = 1
	x = x % p
	while s > 0:
		if s & 1 == 1:
			result = result * x % p
		s = s >> 1
		x = x * x % p
	return result
for i in range(0, T):
	(N, W) = input().split(' ')
	N = int(N)
	W = int(W)
	if W <= 8 and W >= 0:
		num = power(10, N - 2, 1000000007)
		result = num * (9 - W) % 1000000007
	elif W >= -9 and W <= -1:
		num = power(10, N - 2, 1000000007)
		result = num * (10 + W) % 1000000007
	else:
		result = 0
	print(result)


P = 10 ** 9 + 7
T = int(input())
for t in range(T):
	(N, W) = [int(t) for t in input().split()]
	pairs = 0
	for d1 in range(1, 10):
		for dn in range(0, 10):
			if dn - d1 == W:
				pairs += 1
	print(pairs * pow(10, N - 2, P) % P)


def po(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
Mod = 1000000007
t = int(input())
for i in range(t):
	(n, w) = map(int, input().split(' ', 2)[:2])
	if w >= 9 or w < -9:
		print(0)
	elif w < 0:
		ans1 = 10 + w
		ans = ans1 * po(10, n - 2, Mod)
		print(ans % Mod)
	elif w >= 0:
		ans1 = 9 - w
		ans = ans1 * po(10, n - 2, Mod)
		print(ans % Mod)


mod = 1000000007

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
for _ in range(int(input())):
	(n, w) = map(int, input().split())
	if w > 8 or w < -9:
		print(0)
	else:
		if w >= 0:
			m = 9 - w
		else:
			m = 10 - abs(w)
		ans = power(10, n - 2, mod)
		ans %= mod
		ans *= m
		ans %= mod
		print(ans)


for _ in range(int(input())):
	(N, W) = map(int, input().split())
	if W >= 0 and W <= 8:
		print((9 - W) * pow(10, N - 2, 10 ** 9 + 7) % (10 ** 9 + 7))
	elif W < 0 and W >= -9:
		print((10 + W) * pow(10, N - 2, 10 ** 9 + 7) % (10 ** 9 + 7))
	else:
		print(0)


m = 10 ** 9 + 7

def findNumbers(n, w):
	x = 0
	s = 0
	if w >= 0 and w <= 8:
		x = 9 - w
	elif w >= -9 and w <= -1:
		x = 10 + w
	s = pow(10, n - 2, m)
	s *= x % m
	return s % m
for _ in range(int(input())):
	(n, w) = map(int, input().split())
	print(findNumbers(n, w))


MOD = 10 ** 9 + 7

def fastPower(base, idx):
	res = 1
	base %= MOD
	while idx:
		if idx & 1:
			res = res * base % MOD
		base = base * base % MOD
		idx >>= 1
	return res % MOD
for _ in range(int(input())):
	(n, w) = [int(i) for i in input().split()]
	if w < -9 or w > 8:
		print(0)
	else:
		k = 9 - abs(w)
		if w < 0:
			k += 1
		print(k * fastPower(10, n - 2) % MOD)


for _ in range(int(input())):
	(N, W) = map(int, input().split())
	if W < -9 or W > 8:
		print(0)
	else:
		x = 10
		y = N - 2
		p = 1000000007
		if W < 0:
			a = 10 + W
		else:
			a = 9 - W
		res = a
		while y > 0:
			if y & 1:
				res *= x
			y >>= 1
			x = x * x % p
		print(res % p)


m = 10 ** 9 + 7
t = int(input())
for i in range(t):
	(N, W) = map(int, input().split())
	if W >= 0 and W <= 8:
		r = 9 - W
		print(pow(10, N - 2, m) * (r % m) % m)
	elif W > 8:
		print(0)
	elif W < 0 and W >= -9:
		s = 10 - abs(W)
		print(pow(10, N - 2, m) * (s % m) % m)
	else:
		print(0)


t = int(input())
MOD = 1000000007
for _ in range(t):
	(n, w) = [int(x) for x in input().split()]
	if abs(w) > 9 or w == 9:
		print(0)
	elif n - 2 == 0:
		if w >= 0:
			print(9 - w)
		else:
			print(10 + w)
	elif w >= 0:
		print((9 - w) * pow(10, n - 2, MOD) % MOD)
	else:
		print((10 + w) * pow(10, n - 2, MOD) % MOD)


t = int(input())
while t > 0:
	(n, w) = map(int, input().split(' '))
	MOD = 1000000007
	if w >= 0:
		if w > 9:
			print(0)
		else:
			print(pow(10, n - 2, MOD) * (9 - w) % MOD)
	elif w < -9:
		print(0)
	else:
		print(pow(10, n - 2, MOD) * (10 + w) % MOD)
	t = t - 1


mod = int(1000000000.0 + 7)
t = int(input())
while t > 0:
	t -= 1
	(n, w) = map(int, input().split())
	if w > 8 or w < -9:
		s = 0
	else:
		if w < 0:
			w = -(w + 1)
		s = (9 - w) % mod * pow(10, n - 2, mod) % mod
	print(s)


def pow(a, b):
	if b == 0:
		return 1
	t = pow(a, b // 2) % 1000000007
	if b & 1:
		return t * t * a % 1000000007
	else:
		return t * t % 1000000007
for _ in range(int(input())):
	(n, w) = map(int, input().split())
	if w > 9 or w < -9:
		comb = 0
	else:
		lb = max(0, 1 + w)
		ub = min(9, 9 + w)
		comb = max(ub - lb + 1, 0)
	print(pow(10, n - 2) * comb % 1000000007)


t = int(input())

def exp(a, n, mod):
	if n == 0:
		return 1
	elif n == 1:
		return a
	x = exp(a, n // 2, mod)
	if n % 2 == 0:
		x = x * x % mod
	else:
		x = x * x * a % mod
	return x
for x in range(t):
	(n, w) = list(map(int, input().split()))
	if w > 8 or w < -9:
		print(0)
	else:
		count = 0
		mod = 10 ** 9 + 7
		ans = 0
		for i in range(1, 10):
			for j in range(10):
				if j - i == w:
					count += 1
		ans = exp(10, n - 2, mod)
		print(ans * count % mod)


m = 1000000007

def function(na, wa):
	if wa > 8 or wa < -9:
		return 0
	else:
		a = pow(10, na - 2, m)
		if wa >= 0:
			b = 9 - wa
		else:
			b = 9 + wa + 1
		return a * b
	print(a, b)
t = int(input())
while t > 0:
	(n, w) = input().split()
	n = int(n)
	w = int(w)
	ans = function(n, w)
	ans = ans % 1000000007
	print(ans)
	t = t - 1


t = int(input())
for i in range(0, t):
	(n, w) = input().split()
	(n, w) = [int(n), int(w)]
	if w > 8 or w < -9:
		print('0')
	else:
		if w >= 0:
			ans = 9 - w
		else:
			ans = 10 + w
		ans = ans * pow(10, n - 2, 1000000007) % 1000000007
		print(ans)


from sys import stdin, stdout
T = int(input().strip())
mod = 10 ** 9 + 7
for _ in range(T):
	(N, W) = map(int, input().strip().split())
	if W > 8 or W < -9:
		print(0)
	else:
		if W >= 0:
			res = (9 - W) * (10 ** (N - 2) % mod)
		else:
			res = (W + 10) * (10 ** (N - 2) % mod)
		print(res % mod)


import math
from numpy import binary_repr

def f(x, y, z):
	biny = binary_repr(y, width=None)
	biny = biny[::-1]
	k = len(biny)
	sq = x % z * (x % z) % z
	powers = [x, sq]
	for i in range(2, k):
		sq = int(sq % z * (sq % z) % z)
		powers.append(sq)
	ans = 1
	for i in range(0, k):
		if biny[i] == '1':
			ans = ans % z * (powers[i] % z) % z
	return ans % z
t = int(input())
for i in range(0, t):
	(n, W) = map(int, input().split())
	temp = 0
	flag = 1
	if W > 8 or W < -9:
		print(0)
		flag = 0
	elif W >= 0:
		temp = 9 - W
	else:
		temp = 10 + W
	temp = temp % 1000000007 * (f(10, n - 2, 1000000007) % 1000000007) % 1000000007
	if flag == 1:
		print(temp)


cases = int(input())
for i in range(cases):
	data = list(map(int, input().split()))
	numOfDigits = data[0]
	difference = data[1]
	if difference > 8 or difference < -9:
		print(0)
	else:
		if difference >= 0:
			base = 9 - difference
		else:
			base = 10 + difference
		print(base * pow(10, numOfDigits - 2, 10 ** 9 + 7) % (10 ** 9 + 7))


t = int(input())
for i in range(t):
	(n, w) = map(int, input().split())
	li = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -2, -3, -4, -5, -6, -7, -8, -9]
	if w in li:
		if w >= 0:
			c = 9 - w
			print(c * pow(10, n - 2, 1000000007) % 1000000007)
		else:
			c = 10 + w
			print(c * pow(10, n - 2, 1000000007) % 1000000007)
	else:
		print('0')


t = int(input())
for k in range(t):
	(n, w) = map(int, input().split())
	count = 0
	counter = 0
	z = pow(10, 9) + 7
	for i in range(0, 10, 1):
		for j in range(1, 10, 1):
			if i - j == w:
				count += 1
	if n > 2:
		counter = pow(10, n - 2, z)
		counter = counter * count
	elif n == 2:
		counter = count
	print(counter % z)


for i in range(int(input())):
	(n, w) = map(int, input().split())
	c = 0
	m = 10 ** 9 + 7
	if w >= -9 and w <= 8:
		for i in range(1, 10):
			for j in range(10):
				if j - i == w:
					c += 1
		if n == 2:
			print(c)
		elif n > 2:
			c = 10 ** (n - 2) % m * (c % m) % m
			print(c)
	else:
		print(0)


t = int(input())
while t > 0:
	ans = 0
	cnt = 0
	(n, w) = map(int, input().split())
	if w <= 8 or w >= -9:
		for dn in range(0, 10):
			for d1 in range(1, 10):
				if dn - d1 == w:
					cnt = cnt + 1
		ans = pow(10, n - 2, 1000000007)
		ans = ans * cnt % 1000000007
	print(ans)
	t = t - 1


import math
getInputList = lambda : list(input().split())
getInputIntList = lambda : list(map(int, input().split()))
t = int(input())
myset = {}
for i in range(10, 100):
	if i % 10 - i // 10 in myset:
		myset[i % 10 - i // 10] += 1
	else:
		myset[i % 10 - i // 10] = 1
for ts in range(t):
	(n, w) = getInputIntList()
	if w in myset:
		print(myset[w] * pow(10, n - 2, 10 ** 9 + 7) % (10 ** 9 + 7))
	else:
		print(0)


import math
for i in range(int(input())):
	(n, w) = map(int, input().split())
	if w <= 9 and w >= -9:
		if w == 0:
			k = 9
		if w < 0:
			k = 10 + w
		elif w > 0:
			k = 9 - w
		print(k * pow(10, n - 2, 1000000007) % 1000000007)
	else:
		print('0')


d = {}
d[0] = 9
d[1] = 8
d[2] = 7
d[3] = 6
d[4] = 5
d[5] = 4
d[6] = 3
d[7] = 2
d[8] = 1
d[9] = 0
d[-1] = 9
d[-2] = 8
d[-3] = 7
d[-4] = 6
d[-5] = 5
d[-6] = 4
d[-7] = 3
d[-8] = 2
d[-9] = 1

def mod(n):
	return n % (10 ** 9 + 7)
for _ in range(int(input())):
	(n, w) = map(int, input().split())
	if w in d:
		ans = mod(pow(10, n - 2, 10 ** 9 + 7))
		ans = mod(ans * d[w])
		print(ans)
	else:
		print(0)


for _ in range(int(input())):
	(n, w) = input().split()
	n = int(n) - 2
	w = int(w)
	mod = 10 ** 9 + 7
	if w >= 9 or w < -9:
		print(0)
		continue
	if w >= 0:
		k = 9 - w
	else:
		k = 10 + w
	print(int(pow(10, n, mod) * k % (10 ** 9 + 7)))


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	sigma = 1
	if w > 9 or w < -9:
		print(0)
		continue
	sigma = pow(10, n - 2, 1000000007)
	if w >= 0:
		sigma *= 9 - w
	else:
		sigma *= w + 10
	print(sigma % 1000000007)


mod = 10 ** 9 + 7

def power10(N):
	x = bin(N)
	i = -1
	tmp = 10
	r = 1
	while x[i] != 'b':
		if x[i] == '1':
			r *= tmp
			r %= mod
		tmp = tmp % mod * (tmp % mod)
		tmp %= mod
		i -= 1
	return r
from sys import stdin, stdout
T = int(input().strip())
for _ in range(T):
	(N, W) = map(int, input().strip().split())
	dp = [-1] * (N + 1)
	dp[0] = 1
	if W > 8 or W < -9:
		print(0)
	else:
		if W >= 0:
			res = (9 - W) * power10(N - 2)
		else:
			res = (W + 10) * power10(N - 2)
		print(res % mod)


import math
a = int(input())
mod = 10 ** 9 + 7

def power(x, pows):
	res = 1
	while pows > 0:
		if pows % 2 == 1:
			res = res * x % mod
		pows = int(pows / 2)
		x = x * x
	return res
for _ in range(a):
	b = list(map(int, input().split()))
	if b[0] < 2 or (b[1] < -9 or b[1] > 8):
		print(0)
	else:
		aa = b[0] - 2
		count = 0
		cc = pow(10, aa, mod)
		if b[1] < 0:
			count = 9 + b[1] + 1
		else:
			count = 9 - b[1]
		print(count * cc % mod)


def pairs(w):
	pair = 0
	if w == 9 or abs(w) > 9:
		return 0
	elif w >= 0:
		return 9 - w
	else:
		return 10 + w
	return pair
for i in range(int(input())):
	c = input().split()
	w = int(c[1])
	n = int(c[0])
	print(pow(10, n - 2, 1000000007) * pairs(w) % 1000000007)


MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(n, w) = map(int, input().split())
	c = 0
	for i in range(1, 10):
		for j in range(0, 10):
			if j - i == w:
				c += 1
	if n == 2:
		print(c % MOD)
	else:
		print(c % MOD * pow(10, n - 2, MOD) % MOD)


import math
t = int(input())
while t:
	t -= 1
	(n, w) = map(int, input().split())
	if w < -9 or w > 8:
		print(0)
		continue
	else:
		if w < 0:
			res = 10 + w
		else:
			res = 9 - w
		n -= 2
		res = res * pow(10, n, 1000000007) % 1000000007
		print(res)


T = int(input())
while T > 0:
	(N, W) = map(int, input().split())
	Mod = 10 ** 9 + 7
	ans = 0
	if W <= 8 and W >= 0:
		ans = (9 - W) * pow(10, N - 2, Mod)
	elif W < 0 and W >= -9:
		ans = (10 + W) * pow(10, N - 2, Mod)
	print(ans % Mod)
	T = T - 1


mod = 10 ** 9 + 7

def fast(l, t):
	if t == 0:
		return 1
	elif t == 1:
		return l
	else:
		r = fast(l, t // 2)
		if t % 2 == 0:
			return r % 1000000007 * r % 1000000007 % 1000000007 % 1000000007
		else:
			return r % 1000000007 * l * r % 1000000007 % 1000000007 % 1000000007
for i in range(int(input())):
	(n, w) = [int(x) for x in input().split()]
	ans = 0
	middle = fast(10, n - 2)
	for first in range(1, 10):
		for last in range(10):
			if last - first == w:
				ans += 1
	print(ans * middle % mod)


mod = 1000000007
for i in range(int(input())):
	(n, w) = map(int, input().split(' '))
	if abs(w) > 9 or w == 9:
		print(0)
	elif w >= 0:
		print((9 - w) * pow(10, n - 2, mod) % mod)
	else:
		print((10 + w) * pow(10, n - 2, mod) % mod)


try:
	T = int(input())
	m = 10 ** 9 + 7
	ref = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
	for t in range(T):
		var = [int(x) for x in input().split()]
		N = var[0]
		W = var[1]
		if W < 9 and W >= -9:
			val = pow(10, N - 2, m) % m * ref[W] % m % m
			print(val)
		else:
			print(0)
except:
	print('Error')


MOD = int(1000000000.0) + 7

def power(a, b):
	ans = 1
	while b > 0:
		if b & 1:
			ans = ans * a % MOD
		a = a * a % MOD
		b >>= 1
	return ans
t = int(input())
for _ in range(t):
	(n, w) = map(int, input().split())
	if w >= -9 and w <= 8:
		cnt = 0
		for d1 in range(1, 10):
			for dn in range(0, 10):
				if dn - d1 == w:
					cnt += 1
		print(cnt * power(10, n - 2) % MOD)
	else:
		print(0)


m = int(pow(10, 9) + 7)
for i in range(int(input())):
	(n, w) = list(map(int, input().split()))
	s = 0
	for i in range(1, 10):
		for j in range(10):
			if j - i == w:
				s += 1
	print(s * pow(10, n - 2, m) % m)


t = int(input())
for _ in range(t):
	c = 0
	(n, w) = map(int, input().split(' '))
	if abs(w) > 9 or w == 9:
		print(0)
	elif n - 2 == 0:
		if w >= 0:
			print(9 - w)
		else:
			print(10 + w)
	elif w >= 0:
		c = 9 - w
		print(c * pow(10, n - 2, 1000000007) % 1000000007)
	else:
		c = 10 + w
		print(c * pow(10, n - 2, 1000000007) % 1000000007)


t = int(input())
f = 1000000007

def power(n, k):
	s = 1
	while k > 0:
		if k % 2 == 1:
			s = s * n % f
		n = n * n % f
		k = k // 2
	return s
for i in range(0, t):
	l = list(map(int, input().split()))
	n = l[0]
	w = l[1]
	if w >= 0 and w < 9:
		print((9 - w) * power(10, n - 2) % f)
	elif w < 0 and w >= -9:
		print((10 + w) * power(10, n - 2) % f)
	else:
		print(0)


from math import ceil
m = int(pow(10, 9) + 7)
t = int(input())
while t:
	t -= 1
	(n, w) = map(int, input().split())
	ss = 0
	for i in range(1, 10):
		for j in range(10):
			if j - i == w:
				ss += 1
	print(ss * pow(10, n - 2, m) % m)


p = 10 ** 9 + 7
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(range(-9, 10))
	n = 0
	if b in l:
		if b >= 0:
			n = 9 - b
		else:
			n = 10 + b
		print(n * pow(10, a - 2, p) % p)
	else:
		print(0)


t = int(input())
for i in range(t):
	lst = input().split()
	n = int(lst[0])
	w = int(lst[1])
	res = 0
	m = 10 ** 9 + 7
	for j in range(1, 10):
		for k in range(10):
			if k - j == w:
				res += 1
	print(res * 10 ** (n - 2) % m)


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	if w > 8:
		print(0)
	elif w < -9:
		print(0)
	else:
		p = 9 - abs(w)
		digit = n - 2
		mod = 1000000007
		m = pow(10, digit, mod)
		if w < 0:
			print((p + 1) * m % mod)
		else:
			print(p * m % mod)


MOD = 1000000007
t = int(input())
while t > 0:
	(n, w) = list(map(int, input().split()))
	if abs(w) > 9:
		print(0)
	else:
		if w >= 0:
			_val = 9 - w
		else:
			_val = 9 - abs(w) + 1
		_tmp = _val * pow(10, n - 2, MOD) % MOD
		print(_tmp)
	t -= 1


MOD = 1000000007
t = int(input())
for _ in range(t):
	(n, w) = map(int, input().split())
	if w < -9 or w > 8:
		print(0)
	else:
		if w >= 0:
			c = 9 - w
		else:
			c = 10 + w
		ans = c * pow(10, n - 2, MOD) % MOD
		print(ans)


t = int(input())
n = 0
w = 0
p = 0
ans = 0

def powerr(a, b, c):
	res = 1
	a = a % c
	while b > 0:
		if b & 1 == 1:
			res = res * a % c
		b = b >> 1
		a = a * a % c
	return res
for i in range(t):
	(n, w) = map(int, input().split())
	if w < -9 or w > 8:
		print(0)
		continue
	if w < 0:
		p = 10 + w
	else:
		p = 9 - w
	ans = powerr(10, n - 2, 1000000007)
	ans = ans * p % 1000000007
	print(ans)


DIVISOR = 10 ** 9 + 7

def main():
	power_of_9s = [10 ** n % DIVISOR for n in range(1001)]
	T = int(input())
	for t in range(T):
		(N, W) = list(map(int, input().split(' ')))
		if W > 8 or W < -9:
			print(0)
			continue
		if W >= 0:
			first_digits = 9 - W
		elif W < 0:
			first_digits = 10 + W
		mid_digits = power_of_9s[N - 2]
		print(first_digits * mid_digits % DIVISOR)
main()


def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
t = int(input())
while t > 0:
	r = list(map(int, input().split()))
	n = r[0]
	w = r[1]
	if w <= 8 and w >= -9:
		if w >= 0:
			ans = (9 - w) % 1000000007 * (power(10, n - 2, 1000000007) % 1000000007)
			print(ans % 1000000007)
		if w < 0:
			w = w * -1
			ans = (10 - w) % 1000000007 * (power(10, n - 2, 1000000007) % 1000000007)
			print(ans % 1000000007)
	else:
		print(0)
	t = t - 1


def fastexp(x, y):
	res = 1
	while y > 0:
		if y & 1:
			res = res * x % 1000000007
		y = y >> 1
		x = x * x % 1000000007
	return res
for t in range(int(input())):
	(n, w) = map(int, input().split())
	ans = 0
	if w >= 0 and w <= 8:
		ans = (9 - abs(w)) * fastexp(10, n - 2) % 1000000007
	if w < 0 and w >= -9:
		ans = (10 - abs(w)) * fastexp(10, n - 2) % 1000000007
	print(ans)


import math
from itertools import combinations
mod = 10 ** 9 + 7
from sys import stdin, stdout

def modi(a, b, n):
	x = 1
	y = a
	while b > 0:
		if b % 2 == 1:
			x = x * y % n
		y = y * y % n
		b = int(b / 2)
	return x % n

def comb(n, r):
	if n <= 0:
		return 0
	elif n < r:
		return 0
	f = math.factorial
	return f(n) / f(r) / f(n - r)
t = int(input())
while t != 0:
	(n, w) = map(int, input().split(' '))
	z = 9 - abs(w)
	if w >= -9 and w <= 8:
		if w < 0:
			z = z + 1
		print(int(int(z * pow(10, n - 2, mod)) % mod))
	else:
		print(0)
	t = t - 1


t = int(input())
for i in range(0, t):
	(n, W) = map(int, input().split())
	temp = 0
	flag = 1
	if W > 8 or W < -9:
		print(0)
		flag = 0
	elif W >= 0:
		temp = 9 - W
	else:
		temp = 10 + W
	temp = temp % 1000000007 * pow(10, n - 2, 1000000007) % 1000000007
	if flag == 1:
		print(temp)


res = []
M = pow(10, 9) + 7
for i in range(0, int(input())):
	(n, w) = input().split(' ')
	n = int(n)
	w = int(w)
	count = 0
	for k in range(1, 10):
		if k + w < 10 and k + w >= 0:
			count += 1
	res.append(count * pow(10, n - 2, M) % M)
for xx in res:
	print(xx)


t = int(input())
for i in range(0, t):
	(n, w) = map(int, input().split())
	if w < 9 and w >= -9:
		if w >= 0:
			ans = int(9 - abs(w)) * pow(10, n - 2, 10 ** 9 + 7)
			print(ans % (10 ** 9 + 7))
		else:
			ans = int(10 - abs(w)) * pow(10, n - 2, 10 ** 9 + 7)
			print(ans % (10 ** 9 + 7))
	else:
		print('0')


import os
import sys
mod = int(1000000000.0 + 7)

def power(n, p):
	global mod
	ans = 1
	while p > 0:
		if p % 2:
			ans = ans * n % mod
		p //= 2
		n = n * n % mod
	return ans
times = [1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1]
t = int(input())
while t > 0:
	t -= 1
	(n, w) = tuple(map(int, input().split()))
	if w > 8 or w < -9:
		print(0)
		continue
	val = power(10, n - 2)
	print(val * times[w + 9] % mod)


def abc(i, n, w, x, c):
	if c == n:
		return x == w
	ans = 0
	for j in range(10):
		ans += abc(j, n, w, x + j - i, c + 1)
	return ans
e = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, w) = list(map(int, input().split()))
	ans = 0
	for i in range(1, 10):
		pass
	if n == 1:
		if w == 0:
			print(9)
		else:
			print(0)
	elif w >= 9:
		print(0)
	elif w > 0:
		x = (9 - w) * pow(10, n - 2, e) % e
		print(x)
	elif w <= -10:
		print(0)
	elif w == 0:
		print(9 * pow(10, n - 2, e) % e)
	else:
		c = -w
		x = (10 - c) * pow(10, n - 2, e) % e
		print(x)
0


def pow(x, n):
	mod = 10 ** 9 + 7
	ans = 1
	while n > 0:
		if n % 2 == 0:
			x = x % mod * (x % mod) % mod
			n //= 2
		else:
			n -= 1
			ans = ans % mod * (x % mod) % mod
			x = x % mod * (x % mod) % mod
			n //= 2
	return ans
for _ in range(int(input())):
	(n, w) = map(int, input().split())
	wlistpos = [9, 8, 7, 6, 5, 4, 3, 2, 1]
	wlistmin = [0, 9, 8, 7, 6, 5, 4, 3, 2, 1]
	if w >= 9 or w <= -10:
		print(0)
	elif 0 <= w < 9:
		num = wlistpos[w]
		print(num * pow(10, n - 2) % (10 ** 9 + 7))
	else:
		num = wlistmin[abs(w)]
		print(num * pow(10, n - 2) % (10 ** 9 + 7))


t = int(input())
for i in range(t):
	(n, w) = list(map(int, input().strip().split()))
	if abs(w) > 9:
		print(0)
		continue
	if w >= 0:
		x = 9 - w
	else:
		x = 10 + w
	x = x * pow(10, n - 2, 1000000007)
	print(x % 1000000007)


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	if w >= 0 and w <= 8:
		print((9 - w) * pow(10, n - 2, 10 ** 9 + 7) % (10 ** 9 + 7))
	elif w < 0 and w >= -9:
		print((10 + w) * pow(10, n - 2, 10 ** 9 + 7) % (10 ** 9 + 7))
	else:
		print(0)