A squarer is a simple and convenient device. You give it some positive integer X and it calculates its square.
Leha is implementing a module of this device which is responsible for squaring the numbers consisting of multiple repetitions of one digit. But it turned out that it's not as simple as he thought.
Please help him now!

-----Input-----
The first line contains one integer T denoting the number of testcases. The descriptions of T test cases follow.
Each of the following T lines contain 2 space-separated integers - N and D, respectively. It means that the number X in the corresponding testcase consists of the digit D repeated N times (in decimal representation).

-----Output-----
As the answer can be very large, we ask you to output its hash which is computed in the following way:
Let's consider the integer answer Y as a 0-indexed array starting from its leftmost digit. The hash function is calculated as:
p0*Y[0] + p1*Y[1] + ... + pM-1*Y[M-1] modulo 109 + 7 
where M is the length of the array representation of Y and p equals 23.

-----Constraints-----
- 1 ≤ T ≤ 20
- 1 ≤ D ≤ 9
- Subtask 1 (16 points): 1 ≤ N ≤ 9
- Subtask 2 (25 points): 1 ≤ N ≤ 100
- Subtask 3 (27 points): 1 ≤ N ≤ 2 × 104
- Subtask 4 (32 points): 1 ≤ N ≤ 106

-----Example-----
Input:3
1 4
3 6
3 5

Output:139
40079781
32745632

-----Explanation-----
In the first test case, X = 4 and Y = 16. Its hash equals 1*1 + 23*6 = 139.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
val = 10 ** 9 + 7

def MOD(a, b):
	aans = a
	ans = 1
	while b > 0:
		ans = ans * aans % val
		aans = aans * aans % val
		b /= 2
	return ans % val
for i in range(eval(input())):
	(n, d) = list(map(int, input().split()))
	a = int(str(d) * n)
	sqr = str(a * a)
	ans = 0
	count = 0
	for ii in sqr:
		ans = ans + int(ii) * 23 ** count
		count += 1
		z = int(ii) * ans
	print(ans % (10 ** 9 + 7))


T = int(input())
while T > 0:
	[N, D] = list(map(int, input('').split()))
	carry = 0
	cal = 0
	ans = ''
	i = 1
	k = 0
	while i <= N:
		ans += str(chr((carry + i) % 10 + ord('0')))
		carry = int((carry + i) / 10)
		cal += 1
		i += 1
		k += 1
	i -= 2
	while i >= 1:
		ans += str(chr((carry + i) % 10 + ord('0')))
		carry = int((carry + i) / 10)
		cal += 1
		i -= 1
		k += 1
	while carry > 0:
		ans += str((carry + i) % 10 + ord('0'))
		carry = int(carry / 10)
		cal += 1
		k += 1
	ans = int(ans)
	ans *= D * D
	ans = str(ans)
	length = len(ans)
	ans1 = 0
	p = 1
	for i in range(length):
		ans1 = ((ord(ans[i]) - ord('0')) * p + ans1) % 1000000007
		p = p * 23 % 1000000007
	print(ans1)
	T -= 1


tts = [1, 23]
mod = 10 ** 9 + 7
for x in range(2, 2 * 10 ** 6 + 1):
	tts.append(tts[x - 1] * 23 % mod)
t = eval(input())
while t > 0:
	(n, d) = list(map(int, input().split()))
	num = int(str(d) * n)
	num **= 2
	res = 0
	i = 0
	for x in str(num):
		res += int(x) * tts[i]
		i += 1
	print(res % mod)
	t -= 1


def show(n, d):
	t = 0
	m = 1000000007
	for i in range(0, n):
		t = t * 10 + d
	t = t * t
	st = str(t)
	s = 0
	for i in range(0, len(st)):
		s = (s + 23 ** i * int(st[i]) % m) % m
	print(s)

def main():
	t = int(input())
	while t > 0:
		(n, d) = input().split()
		n = int(n)
		d = int(d)
		show(n, d)
		t -= 1
main()


test = eval(input())
while test > 0:
	test = test - 1
	(N, D) = list(map(int, input().strip().split()))
	number = ''
	for i in range(N):
		number = number + str(D)
	num = int(number)
	sq = num * num
	z = str(sq)
	l = len(z)
	ans = 0
	for i in range(l):
		ans = ans + int(z[i]) * 23 ** i
		ans = ans % 1000000007
	print(ans)


def main():
	mod = 10 ** 9 + 7
	for i in range(eval(input())):
		printk = 0
		c = 0
		(A, D) = list(map(int, input().split()))
		aks = int(str(D) * A)
		s = aks * aks
		hey = str(s)
		for ii in hey:
			printk = printk + int(ii) * 23 ** c
			__ = int(ii) * printk
			c += 1
		ok_ = printk % mod
		print(ok_)
main()


test = int(input())
for i in range(0, test):
	(n, k) = list(map(int, input().split()))
	l = str(k) * n
	l = int(l)
	k = l * l
	u = str(k).strip()
	t = len(u)
	j = 1
	ans = 0
	for h in range(0, t):
		ans = ans + int(u[h]) % 1000000007 * (j % 1000000007) % 1000000007 % 1000000007
		j = 23 * j % 1000000007
	print(ans % 1000000007)


mod = 1000000007
dp = []
dp.append(1)
tens = []
tens.append(10)
tws = []
tws.append(1)
for i in range(1, 21):
	tens.append(tens[i - 1] * tens[i - 1])
	dp.append(dp[i - 1] * tens[i - 1] + dp[i - 1])
	tws.append(tws[i - 1] * 2)
t = eval(input())
t = int(t)
for i in range(0, t):
	now = 0
	(b, a) = input().split()
	a = int(a)
	b = int(b)
	j = 20
	val = 0
	while j >= 0:
		if b >= tws[j]:
			val *= tens[j]
			val += dp[j]
			b -= tws[j]
		j -= 1
	val *= a
	act = val * val
	now = str(act)
	dow = 1
	ans = 0
	for c in now:
		x = int(c)
		ans += dow * x
		dow *= 23
		dow %= mod
		ans %= mod
	print(ans)


from math import *
t = int(input())
for i in range(0, t):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	c = ''
	for j in range(1, a + 1):
		c += str(j)
	for j in range(1, a):
		c += str(a - j)
	c = int(c)
	b *= b
	c = c * b
	c = str(c)
	mod = 10 ** 9 + 7
	ans = 0
	for j in range(0, len(c)):
		ans += 23 ** j % mod * (int(c[j]) % mod) % mod
	ans = ans % mod
	print(ans)


MOD = 10 ** 9 + 7
tcase = eval(input())
for times in range(tcase):
	(rep, digit) = list(map(int, input().split()))
	number = str(int(str(digit) * rep) ** 2)
	mult = 1
	ans = 0
	for dig in number:
		ans += int(dig) % MOD * mult % MOD
		mult = mult % MOD * 23 % MOD
	print(ans % MOD)


def square(n, d):
	if n == 1:
		return d * d
	a = ''
	for i in range(1, n + 1):
		a = a + str(i)
	for i in range(n - 1, 0, -1):
		a = a + str(i)
	return d * d * int(a)
t = eval(input())
p = 23
parray = []
parray.append(1)
for i in range(1, 3240001):
	parray.append(parray[i - 1] * p % 1000000007)
for x in range(0, t):
	(n, d) = list(map(int, input().split()))
	sq = square(n, d)
	m = len(str(sq))
	i = 0
	sum = 0
	sqArray = list(map(int, list(str(sq))))
	while i < m:
		sum = (sum + sqArray[m - i - 1] * parray[m - i - 1]) % 1000000007
		i = i + 1
	print('%d' % sum)


import math
import string
MOD = pow(10, 9) + 7
p = 23
MAX = 2 * pow(10, 6) + 10
P = {}
P[0] = 1
for q in range(1, MAX):
	P[q] = P[q - 1] * p % MOD
for _ in range(int(input())):
	(n, d) = list(map(int, input().split()))
	number = [d] * n
	C = [0] * (n + n)
	s = len(C) - 1
	for j in range(n - 1, -1, -1):
		carry = 0
		shift = s
		for i in range(n - 1, -1, -1):
			m = number[i] * number[j]
			summ = m + C[shift] + carry
			num = summ % 10
			c = summ / 10
			C[shift] = num
			carry = c
			shift -= 1
		C[shift] = C[shift] + carry
		s -= 1
	jump = 0
	for i in range(len(C)):
		if C[i] == 0:
			jump += 1
		else:
			break
	C = C[jump:]
	ans = 0
	for i in range(len(C)):
		ans += P[i] * int(C[i]) % MOD
	print(ans % MOD)


test = eval(input())
while test:
	test = test - 1
	(n, d) = list(map(int, input().split()))
	num = 0
	for i in range(n):
		num = num * 10 + d
	sqr = num ** 2
	s = sqr.__str__()
	l = len(s)
	ans = 0
	for i in range(l):
		ans = (ans + 23 ** i * int(s[i])) % 1000000007
	print(ans)


import sys
f = sys.stdin
if len(sys.argv) > 1:
	f = open(sys.argv[1], 'rt')
T = int(f.readline().strip())
MOD = 10 ** 9 + 7

def calc(N, D):
	X = [D] * N
	X_d = [0] * N
	carry = 0
	for i in range(N):
		val = D * D + carry
		X_d[i] = val % 10
		carry = val // 10
	assert carry < 10
	X_d.append(carry)
	product = [0] * (2 * N)
	carry = 0
	cur_sum = 0
	for i in range(N):
		cur_sum += X_d[i]
		val = cur_sum + carry
		product[i] = val % 10
		carry = val // 10
	cur_sum += X_d[N]
	for i in range(N):
		cur_sum -= X_d[i]
		val = cur_sum + carry
		product[N + i] = val % 10
		carry = val // 10
	while carry > 0:
		product.append(carry % 10)
		carry = carry // 10
	while product and product[-1] == 0:
		del product[-1]
	h = 0
	for x in product:
		h = (h * 23 + x) % MOD
	return h
for case_id in range(1, T + 1):
	(N, D) = list(map(int, f.readline().strip().split()))
	r = calc(N, D)
	print(r)


import sys
mod = 10 ** 9 + 7
l = [1]
for i in range(1, 10 ** 6 + 1):
	l.append(l[-1] * 23 % mod)

def solve(num):
	length = len(num)
	ans = 0
	for i in range(length):
		ans += l[i] * int(num[i])
		ans %= mod
	return ans
for cases in range(int(sys.stdin.readline())):
	(n, d) = list(map(int, sys.stdin.readline().split()))
	num = int(str(d) * n) % mod
	num = num ** 2
	print(solve(str(num)))