On her way to ChefLand, Marichka noticed $10^K$ road signs (numbered $0$ through $10^K - 1$). For each valid $i$, the sign with number $i$ had the integer $i$ written on one side and $10^K-i-1$ written on the other side.
Now, Marichka is wondering — how many road signs have exactly two distinct decimal digits written on them (on both sides in total)? Since this number may be large, compute it modulo $10^9+7$.
For example, if $K = 3$, the two integers written on the road sign $363$ are $363$ and $636$, and they contain two distinct digits $3$ and $6$, but on the road sign $362$, there are integers $362$ and $637$, which contain four distinct digits — $2$, $3$, $6$ and $7$. On the road sign $11$, there are integers $11$ and $988$, which contain three distinct digits — $1$, $9$ and $8$.

-----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 a single integer $K$.

-----Output-----
For each test case, print a single line containing one integer — the number of road signs with exactly two digits, modulo $10^9+7$.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le K \le 10^9$

-----Subtasks-----
Subtask #1 (20 points): $1 \le T, K \le 5$
Subtask #2 (80 points): original constraints

-----Example Input-----
1
1

-----Example Output-----
10

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code:

Solutions:
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())
mod = 10 ** 9 + 7
for i in range(t):
	k = int(input())
	print(10 * power(2, k - 1, mod) % mod)


t = int(input())
for _ in range(t):
	MOD = 1000000007

	def powerLL(x, n):
		result = 1
		while n:
			if n & 1:
				result = result * x % MOD
			n = int(n / 2)
			x = x * x % MOD
		return result
	sa = 2
	k = int(input())
	k = k - 1
	sb = int(k)
	result = 10 % MOD * powerLL(sa, sb) % MOD
	print(result)


[print(pow(2, int(input()) - 1, 1000000007) * 10 % 1000000007) for _ in range(int(input()))]


t = int(input())
while t > 0:
	n = 1000000007
	m = int(input())
	r = pow(2, m, n)
	r = r * 5 % n
	print(r)
	t = t - 1


from sys import stdin

def szybkie_pot(p, w, m):
	wynik = 1
	while w > 0:
		if w % 2:
			wynik = wynik * p % m
		w = w // 2
		p = p * p % m
	return wynik
il_t = int(stdin.readline())
for i in range(il_t):
	k = int(stdin.readline())
	print(10 * szybkie_pot(2, k - 1, 1000000007) % 1000000007)


from sys import stdin, stdout

def power(x, p):
	res = 1
	while p:
		if p & 1:
			res = res * x % 1000000007
		x = x * x % 1000000007
		p >>= 1
	return res
for _ in range(int(stdin.readline())):
	k = int(stdin.readline())
	mod = 10 ** 9 + 7
	result = 5 * power(2, k)
	result = result % mod
	print(result)


l = int(input())
for x in range(l):
	a = int(input())
	print(10 * pow(2, a - 1, int(1000000000.0 + 7)) % int(1000000000.0 + 7))


from heapq import heapify, heappush, heappop
from cmath import pi
from distutils import extension
import sys
from math import gcd, sqrt, log10, log2, floor, ceil
from collections import deque, defaultdict
from tkinter.tix import Tree
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

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

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
for l in rg(ii()):
	k = ii()
	print(5 % mod * a_pwr_n(2, k, mod) % mod % mod)


t = int(input())
for i in range(t):
	k = int(input())
	print(10 * pow(2, k - 1))


def bigpow(n, p, m):
	if p == 0:
		return 1
	elif p == 1:
		return n
	elif p % 2 == 0:
		tmp = bigpow(n, p // 2, m)
		return tmp * tmp % m
	else:
		return n * (bigpow(n, p - 1, m) % m) % m
tc = int(input().strip())
for t in range(tc):
	k = int(input().strip())
	m = int(1000000000.0 + 7)
	ans = 10 * bigpow(2, k - 1, m) % m
	print(ans)


def intpow(base, exp):
	if exp == 0:
		return 1
	elif exp == 1:
		return base
	elif exp & 1 != 0:
		return base * intpow(base * base % 1000000007, exp >> 1) % 1000000007
	else:
		return intpow(base * base % 1000000007, exp >> 1) % 1000000007
mod = 1000000007
T = int(input())
for _t in range(T):
	K = int(input())
	answer = 5 * intpow(2, K) % mod
	print(answer)


while True:
	try:
		T = int(input())
		for i in range(T):
			K = int(input())
			a = pow(2, K - 1, 1000000007)
			print(a * 10 % 1000000007)
	except EOFError:
		break


[print(10 * pow(2, int(input()) - 1, int(1000000000.0 + 7)) % int(1000000000.0 + 7)) for i in range(int(input()))]


tests = int(input())
mod_num = 1000000007

def get_power_of_two(power):
	res = 1
	x = 2
	while power > 0:
		if power & 1 == 1:
			res = res * x % mod_num
		power = power >> 1
		x = x * x % mod_num
	return res
for _ in range(tests):
	K = int(input())
	print('{}'.format(10 * get_power_of_two(K - 1) % mod_num))


T = int(input())
for qweqww in range(T):
	k = int(input())
	an = pow(2, k - 1, 10 ** 9 + 7)
	an = an * 10
	an = an % (10 ** 9 + 7)
	print(an)


t = int(input())
mod = 10 ** 9 + 7

def fun(x, p):
	ret = 1
	while p:
		if p & 1:
			ret = ret * x % mod
		x = x * x % mod
		p >>= 1
	return ret
for i in range(t):
	n = int(input())
	x = fun(2, n)
	x = 5 * x % mod
	print(x)


t = int(input())
while t != 0:
	k = int(input())
	f = pow(2, k - 1, 1000000007)
	f = f * 10 % 1000000007
	print(f)
	t -= 1


__author__ = 'Prateek'

def test():
	k = int(input())
	ans = pow(2, k - 1, int(10 ** 9 + 7)) * 10 % int(10 ** 9 + 7)
	print(ans)
if __author__ == 'Prateek':
	t = int(input())
	for _ in range(t):
		test()


for i in range(int(input())):
	n = int(input())
	m = 10 ** 9 + 7
	print(10 * 2 ** (n - 1) % m)


t = int(input())
m = 1000000007
for ijirj in range(t):
	k = int(input())
	print(5 * pow(2, k, m) % m)


def power(x, y):
	if y == 0:
		return 1
	temp = power(x, y // 2)
	if y % 2 == 0:
		return temp * temp % 1000000007
	else:
		return x * temp * temp % 1000000007
t = int(input())
ans = []
for j in range(t):
	k = int(input())
	c = 10 * power(2, k - 1)
	ans.append(c)
for i in range(len(ans)):
	print(ans[i] % 1000000007)


t = int(input())

def power(a, n):
	ans = 1
	for i in range(n):
		ans *= a
	return ans
for i in range(t):
	k = int(input())
	print(10 * power(2, k - 1))


mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	k = int(input())
	print(10 * pow(2, k - 1, mod) % mod)


import math

def com():
	a = []
	p = 10
	m = 1000000007
	a.append(10)
	for i in range(1, 100):
		p = a[i - 1] % m
		p = p * 2 % m
		p = p % m
		a.append(p)
	return a
t = int(input())
a = com()
while t > 0:
	k = int(input())
	c = a[k - 1]
	print(c)
	t -= 1


import math
t = int(input())
while t > 0:
	n = int(input())
	p = pow(2, n - 1, 1000000007) * 10
	p = p % 1000000007
	print(p)
	t = t - 1


t = int(input())
for _ in range(t):
	K = int(input())
	K -= 1
	A = 2
	B = 10
	M = 10 ** 9 + 7
	while K > 0:
		if K % 2 != 0:
			B = B * A % M
			K -= 1
		else:
			A = A ** 2 % M
			K //= 2
	print(B)


m = 10 ** 9 + 7
t = int(input())
for i in range(t):
	k = int(input())
	print(5 * pow(2, k, m) % m)


t = int(input())
for i in range(t):
	n = int(input())
	m = int(1000000000.0 + 7)
	t = 5 * pow(2, n, m)
	a = t % m
	print(a)


m = 10 ** 9 + 7
for _ in range(int(input())):
	K = int(input())
	a = 10 * pow(2, K - 1, m) % m
	print(a)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	k = int(input())
	ans = 5 * pow(2, k, mod) % mod
	print(ans)


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())):
	a = 10
	r = 2
	k = int(input())
	print(a * power(r, k - 1, 10 ** 9 + 7) % (10 ** 9 + 7))


import sys
M = 1000000007

def pow_mod(x, y):
	n = 1
	while y:
		if y & 1:
			n = n * x % M
		x = x * x % M
		y >>= 1
	return n
for i in range(int(sys.stdin.readline())):
	k = int(sys.stdin.readline())
	ans = 5 * pow_mod(2, k) % M
	print(ans)


t = int(input())
M = 10 ** 9 + 7
for _ in range(t):
	k = int(input())
	n = pow(2, k, M)
	n = n * 5 % M
	print(n)


mod = 10 ** 9 + 7

def power(x, p):
	ans = 1
	while p:
		if p & 1:
			ans = ans * x % mod
		x = x * x % mod
		p >>= 1
	return ans
for z in range(int(input())):
	k = int(input())
	ans = 10 * power(2, k - 1) % mod
	print(ans)


t = int(input())
for tt in range(t):
	num = int(input())
	print(10 * pow(2, num - 1, 10 ** 9 + 7) % (10 ** 9 + 7))


t = int(input())

def power(a, n):
	if n == 0:
		return 1
	elif n == 1:
		return a
	else:
		r = power(a, n // 2)
		if n % 2 == 0:
			return r * r
		else:
			return r * a * r
for i in range(t):
	k = int(input())
	print(10 * power(2, k - 1))


T = int(input())
while T:
	K = int(input())
	print(10 * pow(2, K - 1, 1000000007) % 1000000007)
	T -= 1


import math as mt
import heapq
from functools import lru_cache

@lru_cache(maxsize=1 << 20)
def modex(a, b, m):
	r = 1
	while b:
		if b & 1:
			r = r * a % m
		b >>= 1
		a = a * a % m
	return r
import sys
intinp = lambda : int(input())

def listinp(func=int):
	return list(map(func, input().split()))

def nsepline(n, func=str):
	return [func(input()) for _ in range(n)]

def printlist(li, glue=' '):
	return glue.join(list(map(str, li)))

def fop(s, end='\n'):
	sys.stdout.write(str(s) + end)

def fip():
	return sys.stdin.readline().strip()
fintinp = lambda : int(fip())

def flistinp(func=int):
	return list(map(func, fip().split()))

def fnsepline(n, func=str):
	return [func(fip()) for _ in range(n)]
ntc = fintinp()
mod = int(1000000000.0 + 7)
for _ in range(ntc):
	k = fintinp()
	fop(5 * modex(2, k, mod) % mod)


MOD = 10 ** 9 + 7
t = int(input())
while t > 0:
	n = int(input())
	print(10 * pow(2, n - 1, MOD) % MOD)
	t -= 1


mod = 10 ** 9 + 7
for t in range(int(input())):
	n = int(input())
	print(pow(2, n - 1, mod) * 10 % mod)


mod = 1000000007

def pw(x, y):
	ans = 1
	while y:
		if y & 1:
			ans = ans * x % mod
		x = x * x % mod
		y = y // 2
	return ans
t = int(input())
while t:
	n = int(input())
	print(10 * pw(2, n - 1) % mod)
	t = t - 1


MOD = 1000000007

def powmod(n, m):
	pow2 = 2
	result = 1
	while n > 0:
		if n % 2 == 1:
			result = result * pow2 % m
		pow2 = pow2 * pow2 % m
		n >>= 1
	return result
for _ in range(int(input())):
	k = int(input())
	sol = powmod(k - 1, MOD)
	print(sol * 10 % MOD)


from sys import stdin, stdout

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sin():
	return stdin.readline()

def out(s):
	stdout.write(str(s) + '\n')
m = 1000000007
for i in range(int(input())):
	n = sin()[:-1]
	remainderB = 0
	for i in range(len(n)):
		remainderB = (remainderB * 10 + ord(n[i]) - 48) % (m - 1)
	out(power(2, remainderB, m) * 5 % m)


mod = 1000000007
t = int(input())
for i in range(t):
	k = int(input())
	a = pow(2, k - 1, mod)
	b = 10 * a % mod
	print(b)


from sys import stdin, stdout
inn = stdin.readline
out = stdout.write
for i in range(int(inn())):
	n = int(inn())
	m = 10 ** 9 + 7
	for i in range(1, n + 1):
		v = 10 * pow(2, n - 1, m) % m
	out(str(v) + '\n')


t = int(input())
m = 1000000007
for i in range(0, t):
	n = int(input())
	print(pow(2, n - 1, m) * 10 % m)


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())
for x in range(t):
	k = int(input())
	val = power(2, k - 1, 1000000007) * 10
	val = val % 1000000007
	print(val)


def power(x, y, mod):
	res = 1
	x = x % mod
	while y > 0:
		if y & 1:
			res = res * x % mod
		y = y >> 1
		x = x * x % mod
	return res
T = int(input())
for x in range(T):
	k = int(input())
	b = str(k - 1)
	remainderB = 0
	MOD = 1000000007
	for i in range(len(b)):
		remainderB = (remainderB * 10 + int(b[i])) % (MOD - 1)
	ans = power(2, remainderB, MOD) * 10
	print(ans % MOD)


from sys import stdin, stdout

def sin():
	return stdin.readline()

def out(s):
	stdout.write(str(s) + '\n')
m = 1000000007
for i in range(int(input())):
	n = int(sin())
	print(2 ** n * 5 % m)


def power(val, p, mod):
	ans = 1
	while p:
		if p & 1:
			ans = ans * val % mod
		val = val * val % mod
		p >>= 1
	return ans
t = int(input())
for i in range(t):
	k = int(input())
	print(10 * power(2, k - 1, 1000000007) % 1000000007)


m = 1000000007
for _ in range(int(input())):
	k = int(input())
	print(5 * pow(2, k, m) % m)


m = int(1000000000.0 + 7)
for _ in range(int(input())):
	k = int(input())
	x = 2
	res = 10
	a = res * pow(x, k - 1, m)
	t = a % m
	print(t)


def pw(x, p):
	ret = 1
	while p:
		if p & 1:
			ret = ret * x % mod
		x = x * x % mod
		p >>= 1
	return ret
mod = 1000000007
T = int(input())
for _t in range(T):
	K = int(input())
	answer = 5 * pw(2, K) % mod
	print(answer)


t = int(input())
a = 10 ** 9 + 7

def fun(n, k, a):
	if k == 0:
		return 1
	elif k == 1:
		return n
	else:
		x = fun(n, int(k / 2), a)
		if k % 2 == 0:
			return x % a * (x % a) % a
		else:
			return x % a * (x % a) * (n % a) % a
for i in range(t):
	n = int(input())
	x = fun(2, n, a)
	x = 5 * x % a
	print(x)


t = int(input())
for i in range(t):
	k = int(input())
	res = pow(2, k) * 5 % 1000000007
	print(res)


def Modular(x, n, m):
	if n == 0:
		return 1
	elif n % 2 == 0:
		y = Modular(x, n / 2, m)
		return y * y % m
	else:
		return x % m * Modular(x, n - 1, m) % m
test = int(input())
r = 2
a = 10
for i in range(test):
	n = int(input())
	ans = 10 % (10 ** 9 + 7) * Modular(r, n - 1, 10 ** 9 + 7) % (10 ** 9 + 7)
	print(ans)


from sys import stdin, stdout

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(stdin.readline())
AllInp = stdin.readlines()
A = []
for Inp in AllInp:
	k = int(Inp)
	A.append(str(10 * power(2, k - 1, 10 ** 9 + 7) % (10 ** 9 + 7)))
print('\n'.join(A))


import sys
M = int(1000000000.0) + 7
for i in range(int(sys.stdin.readline())):
	k = int(sys.stdin.readline())
	ans = 5 * pow(2, k, M) % M
	print(ans)


t = int(input())
for _ in range(t):
	k = int(input())
	m = int(1000000000.0 + 7)
	a = 10
	r = 2
	t = a * pow(r, k - 1, m)
	ans = t % m
	print(ans)


p = int(1000000000.0 + 7)

def moduloMultiplication(a, b, mod):
	res = 0
	a = a % mod
	while b:
		if b & 1:
			res = (res + a) % mod
		a = 2 * a % mod
		b >>= 1
	return res
t = int(input())
while t:
	k = int(input())
	ans = moduloMultiplication(10, pow(2, k - 1, p), p)
	print(ans)
	t -= 1


mod = 1000000000 + 7
for _ in range(int(input())):
	n = int(input())
	a = 10 * pow(2, n - 1, mod)
	print(a % mod)


mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	k = int(input())
	re = pow(2, k, mod)
	re = re * 5
	re = re % mod
	print(re)


def get_power(n, m, D):
	if n == 0:
		return 1
	elif n == 1:
		return 2
	elif n in D:
		return D[n]
	else:
		D[n] = get_power(n // 2, m, D) % m * (get_power(n - n // 2, m, D) % m) % m
		return D[n]
T = int(input())
ans = []
m = 10 ** 9 + 7
for _ in range(T):
	K = int(input())
	ans.append(get_power(K, m, {}) * 5 % m)
for i in ans:
	print(i)


for _ in range(int(input())):
	x = int(input())
	print(5 * pow(2, x, 10 ** 9 + 7) % (10 ** 9 + 7))


n = int(input())
for i in range(n):
	x = int(input())
	m = 1000000007
	ans = 5 * pow(2, x, m)
	ans = ans % m
	print(ans)


import math
t = int(input())
while t > 0:
	k = int(input())
	j = 0
	h = math.pow(10, k) - 1
	h = int(h)
	c = 0
	for i in range(h + 1):
		ab = []
		if i == 0:
			if i not in ab:
				ab.append(i)
			p = h - i
			while p > 0:
				g = p % 10
				if g not in ab:
					ab.append(g)
				p = p // 10
		elif i == h:
			if i not in ab:
				ab.append(h - i)
			p = i
			while p > 0:
				g = p % 10
				if g not in ab:
					ab.append(g)
				p = p // 10
		else:
			p = i
			while p > 0:
				g = p % 10
				if g not in ab:
					ab.append(g)
				p = p // 10
			p = h - i
			while p > 0:
				g = p % 10
				if g not in ab:
					ab.append(g)
				p = p // 10
		if len(ab) == 2:
			c += 1
	print(c)
	t -= 1


c = 10 ** 9 + 7

def exponentMod(a, b):
	if a == 0:
		return 0
	if b == 0:
		return 1
	y = 0
	if b % 2 == 0:
		y = exponentMod(a, b // 2)
		y = y * y % c
	else:
		y = a % c
		y = y * exponentMod(a, b - 1) % c % c
	return (y + c) % c
for _ in range(int(input())):
	n = int(input())
	a = 2
	b = n - 1
	val = exponentMod(a, b)
	print(val * 10 % c)


mod = 10 ** 9 + 7

def fun(x, y):
	m = 1
	a = 1
	while y > 0:
		if y & m == 1:
			a = a * x
		y = y >> 1
		x = x % 1000000007 * (x % 1000000007) % 1000000007
	return a % mod
t = int(input())
while t:
	n = int(input())
	a = 10
	r = 2
	print(a % mod * fun(2, n - 1) % mod % mod)
	t -= 1


m = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	k = int(input())
	a = 10 * pow(2, k - 1, m) % m
	print(a)


T = input()
t = int(T)
ans = []
for i in range(t):
	K = input()
	k = int(K)
	ans.append(10 % (pow(10, 9) + 7) * pow(2, k - 1, pow(10, 9) + 7) % (pow(10, 9) + 7))
for i in range(t):
	print(ans[i])


p = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	k = int(input())
	r = pow(2, k - 1, p)
	print(r * 10 % p)


MOD = 1000000007

def fast_power(base, power):
	if power == 0:
		return 1
	temp = fast_power(base, power // 2)
	if power % 2 == 0:
		return temp * temp % MOD
	else:
		return base * temp * temp % MOD
for i in range(int(input())):
	K = int(input())
	if K == 1:
		print(10)
	elif K == 2:
		print(20)
	else:
		t = fast_power(2, K - 3)
		print(40 * t % MOD)


t = int(input())
for _ in range(t):
	k = int(input())
	mod = 1000000007
	ans = pow(2, k - 1, mod)
	ans = ans * 10
	ans = ans % 1000000007
	print(ans)


mod = int(1000000000.0 + 7)
t = int(input())
for _ in range(t):
	n = int(input())
	ans = 10 * pow(2, n - 1, mod) % mod
	print(ans)


def __starting_point():
	tc = int(input().strip())
	for t in range(tc):
		k = int(input().strip())
		ans = 10
		mod = int(1000000000.0 + 7)
		for i in range(1, k):
			ans = 2 * (ans % mod) % mod
		print(ans)
__starting_point()


def power(x, y):
	s = 1
	while y:
		if y & 1:
			s = s * x % k
		y >>= 1
		x = x * x % k
	return s % k
t = int(input())
k = 1000000007
while t:
	t -= 1
	n = int(input())
	ans = power(2, n - 1) * 10
	print(int(ans % k))


def power(x, p):
	ret = 1
	while p:
		if p & 1:
			ret = ret * x % 1000000007
		x = x * x % 1000000007
		p >>= 1
	return ret
t = int(input())
for i in range(t):
	n = int(input())
	print(10 * power(2, n - 1) % 1000000007)


import math
mod = 10 ** 9 + 7
for i in range(int(input())):
	k = int(input())
	print(5 * pow(2, k, mod) % mod)


T = int(input())
while T:
	K = int(input())
	m = 1000000007
	res = 5 * pow(2, K, m)
	res = res % m
	print(res)
	T -= 1


try:
	import sys

	def power(x, p):
		res = 1
		while p:
			if p & 1:
				res = res * x % 1000000007
			x = x * x % 1000000007
			p >>= 1
		return res
	test = int(sys.stdin.readline())
	for _test in range(test):
		K = int(sys.stdin.readline())
		answer = 5 * power(2, K) % 1000000007
		print(answer)
except:
	pass


for t in range(int(input())):
	k = int(input())
	num = 10
	d = pow(2, k - 1, 1000000007)
	print(10 * d % 1000000007)