The Petrozavodsk camp takes place in about one month. Jafar wants to participate in the camp, but guess what? His coach is Yalalovichik.
Yalalovichik is a legendary coach, famous in the history of competitive programming. However, he is only willing to send to the camp students who solve really hard problems on Timus. The deadline that Yalalovichik set before has passed and he refuses to send Jafar to the camp.
Jafar decided to make Yalalovichik happy in hopes of changing his decision, so he invented a new sequence of numbers and named them Yalalovichik numbers. Jafar is writing a research paper about their properties and wants to publish it in the Science Eagle yearly journal.
A Yalalovichik number is created in the following way:
- Consider an integer $N$ in decimal notation; let's call it the base of the Yalalovichik number $Y_N$. $N$ may not contain the digit $0$.
- Treat $N$ as a decimal string. Compute all left shifts of this string $N_0, N_1, \ldots, N_{|N|-1}$ ($|N|$ denotes the number of digits of $N$); specifically, $N_k$ denotes the string formed by moving the first $k$ digits of $N$ to the end in the same order.
- Concatenate the strings $N_0, N_1, \ldots, N_{|N|-1}$. The resulting string is the decimal notation of $Y_N$.
For example, if $N = 123$, the left shifts are $123, 231, 312$ and thus $Y_N = 123231312$.
You are given the base $N$. Calculate the value of $Y_N$ 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 a single decimal integer $N$.

-----Output-----
For each test case, print a single line containing one integer — the value of the Yalalovichik number $Y_N$ modulo $10^9+7$.

-----Constraints-----
- $1 \le T \le 200$
- $|N| \le 10^5$
- $N$ does not contain the digit $0$
- the sum of $|N|$ over all test cases does not exceed $10^6$

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

-----Example Output-----
123231312

Difficulty: HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
M = 10 ** 9 + 7
N = 100001
p10 = [None] * N
p10[0] = 1
for i in range(1, N):
	p10[i] = p10[i - 1] * 10 % M
t = int(input())
for _ in range(t):
	s = list(map(ord, input()))
	p = sum(((x - 48) * y for (x, y) in zip(reversed(s), p10)))
	m = p10[len(s)]
	r = 0
	for d in s:
		r = (r * m + p) % M
		p = (p * 10 - (m - 1) * (d - 48)) % M
	print(r)


from operator import mul
M = 10 ** 9 + 7
N = 100001
p10 = [None] * N
k = 1
for i in range(N):
	p10[i] = k
	k = k * 10 % M
t = int(input())
for _ in range(t):
	s = list(map(int, input()))
	m = p10[len(s)]
	p = sum(map(mul, reversed(s), p10))
	r = 0
	for d in s:
		r = (r * m + p) % M
		p = (p * 10 - (m - 1) * d) % M
	print(r)


import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = input()
	mod = 10 ** 9 + 7
	cur_n = n[-1] + n[:-1]
	n1 = len(cur_n)
	ans = 0
	a = 1
	c = 10 ** n1 % mod
	d = 10 ** (n1 - 1) % mod
	t = pow(10, mod - 2, mod)
	for i in cur_n[::-1]:
		cur_n = int(cur_n)
		ans += cur_n * a % mod
		cur_n -= int(i)
		cur_n = cur_n * t % mod
		cur_n += int(i) * d
		cur_n = cur_n % mod
		a *= c
		a = a % mod
	print(ans % mod)


M = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	s = list(map(int, input()))
	(p, m) = (0, 1)
	for d in reversed(s):
		p += d * m
		m = m * 10 % M
	ans = 0
	for d in s:
		ans = (ans * m + p) % M
		p = (p * 10 - (m - 1) * d) % M
	print(ans)


T = int(input())
for i in range(T):
	N = int(input())
	ans = N
	M = N
	L = len(str(N))
	ls = list(str(N))
	key = 10 ** L % (10 ** 9 + 7)
	for i in range(L - 1):
		a0 = int(ls[i])
		M = (10 * M + a0 * (1 - key)) % (10 ** 9 + 7)
		ans = (ans * key + M) % (10 ** 9 + 7)
	print(ans % (10 ** 9 + 7))


a = [1]
z = 10 ** 9 + 7
for i in range(1, 10 ** 5 + 1):
	a.append(10 * a[i - 1] % z)
t = int(input())
for i in range(t):
	p = input()
	n = len(p)
	b = int(p)
	s = b
	for i in range(n - 1):
		b = b - a[n - 1] * int(p[i]) % z
		if b < 0:
			b = b + z
		b = (10 * b + int(p[i])) % z
		s = (s * a[n] + b) % z
	print(s)


M = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	s = input()
	(p, m) = (0, 1)
	for d in reversed(s):
		p += (ord(d) - 48) * m
		m = m * 10 % M
	r = 0
	for d in s:
		r = (r * m + p) % M
		p = (p * 10 - (m - 1) * (ord(d) - 48)) % M
	print(r)


for a in range(int(input())):
	n = input()
	size = len(n)
	N = int(n)
	modulous = 10 ** 9 + 7
	(NSH, resultSH) = (10 ** (size - 1) % modulous, 10 ** size % modulous)
	N %= modulous
	result = N
	for x in range(size - 1):
		tmp = int(n[x]) * NSH % modulous
		tmp = (N - tmp) % modulous
		tmp = tmp * 10 % modulous
		tmp = (tmp + int(n[x])) % modulous
		N = tmp
		result = (result * resultSH + N) % modulous
	print(result)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = input()
	cur_n = n[-1] + n[:-1]
	n1 = len(cur_n)
	ans = 0
	a = 1
	c = pow(10, n1, mod)
	d = pow(10, n1 - 1, mod)
	t = pow(10, mod - 2, mod)
	for i in cur_n[::-1]:
		cur_n = int(cur_n)
		ans += cur_n * a % mod
		cur_n -= int(i)
		cur_n = cur_n * t % mod
		cur_n += int(i) * d
		cur_n = cur_n % mod
		a *= c
		a = a % mod
	print(ans % mod)


for _ in range(int(input())):
	N = input()
	(M, l, ans, x) = (10 ** 9 + 7, len(N), 0, 1)
	for i in range(l):
		ans = (ans * 10 + ord(N[i]) - 48) % M
		if i != l - 1:
			x = x * 10 % M
	result = ans
	for i in range(l - 1):
		result = ((result - (ord(N[i]) - 48) * x) * 10 + ord(N[i]) - 48) % M
		ans = (ans * x * 10 + result) % M
	print(ans)


t = int(input())

def func(st):
	ans = 0
	for i in range(k):
		temp = int(n[i]) * decimal[k - i - 1]
		if temp >= mod:
			temp %= mod
		ans += temp
		if ans >= mod:
			ans %= mod
	return ans
mod = 10 ** 9 + 7
decimal = [1]
for i in range(10 ** 5 + 1):
	temp = decimal[-1] * 10
	if temp >= mod:
		temp %= mod
	decimal.append(temp)
while t:
	t -= 1
	n = input()
	k = len(n)
	mul = [1]
	power = 10 ** k % mod
	power_1 = 10 ** (k - 1) % mod
	for i in range(k):
		temp = mul[-1] * power
		if temp >= mod:
			temp %= mod
		mul.append(temp)
	flag = k < 10
	ans = 0
	val = func(n)
	for i in range(k - 1, -1, -1):
		temp = val * mul[i]
		if temp >= mod:
			temp %= mod
		ans += temp
		if ans >= mod:
			ans %= mod
		val = val - int(n[k - 1 - i]) * power_1
		val = (val * 10 + int(n[k - 1 - i])) % mod
	print(ans % mod)


from bisect import bisect_right as br
from bisect import bisect_left as bl
from collections import defaultdict
from itertools import combinations
import functools
import sys
import math
MAX = sys.maxsize
MAXN = 10 ** 6 + 10
MOD = 10 ** 9 + 7

def isprime(n):
	n = abs(int(n))
	if n < 2:
		return False
	if n == 2:
		return True
	if not n & 1:
		return False
	for x in range(3, int(n ** 0.5) + 1, 2):
		if n % x == 0:
			return False
	return True

def mhd(a, b, x, y):
	return abs(a - x) + abs(b - y)

def numIN():
	return map(int, sys.stdin.readline().strip().split())

def charIN():
	return sys.stdin.readline().strip().split()
t = [0] * 1000010

def create(a, n):
	global t
	for i in range(n, 2 * n):
		t[i] = a[i - n]
	for i in range(n - 1, 0, -1):
		t[i] = t[2 * i] + t[2 * i + 1]

def cal(n, k):
	res = 1
	c = [0] * (k + 1)
	c[0] = 1
	for i in range(1, n + 1):
		for j in range(min(i, k), 0, -1):
			c[j] = (c[j] + c[j - 1]) % MOD
	return c[k]
for i in range(int(input())):
	n = int(input())
	a = str(n)
	l = len(a)
	ans = n
	p1 = pow(10, l, MOD)
	p2 = pow(10, l - 1, MOD)
	for j in range(l - 1):
		n -= int(a[j]) * p2
		n %= MOD
		n *= 10
		n %= MOD
		n += int(a[j])
		n %= MOD
		ans *= p1
		ans %= MOD
		ans += n
		ans %= MOD
	print(ans)


mod = 1000000007
for _ in range(int(input())):
	s = input()
	l = len(s)
	n = int(s) % mod
	q = pow(10, l - 1, mod)
	x = 0
	for i in range(l):
		x = x * (q * 10) % mod % mod
		x = (x + n) % mod
		n = ((n - int(s[i]) * q % mod) * 10 + int(s[i])) % mod
	print(x % mod)


t = int(input())
mod10 = [1]
p = 10 ** 9 + 7
for i in range(1, 10 ** 5 + 1):
	temp = 10 * mod10[i - 1] % p
	mod10.append(temp)

def res(n):
	l = len(n)
	a = [int(n[l - 1])]
	for j in range(l - 2, -1, -1):
		a.append((mod10[l - 1 - j] * int(n[j]) + a[-1]) % p)
	return a

def res1(n):
	l = len(n)
	a = [0, int(n[0])]
	for j in range(1, l - 1):
		a.append((10 * a[-1] + int(n[j])) % p)
	return a
for i in range(t):
	n = input()
	x = ''
	l = len(n)
	a = res(n)
	b = res1(n)
	count = 0
	y = 0
	while count < l:
		y = (y + (mod10[l - count - 1] * a[count] % p + b[l - count - 1]) * pow(10, count * l, p)) % p
		count = count + 1
	print(y % p)


M = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	s = list(map(lambda x: ord(x) - 48, input()))
	(p, m) = (0, 1)
	for d in reversed(s):
		p += d * m
		m = m * 10 % M
	r = 0
	for d in s:
		r = (r * m + p) % M
		p = (p * 10 - (m - 1) * d) % M
	print(r)


m = 10 ** 9 + 7
T = int(input())
while T > 0:
	num = list(map(int, input()))
	n = 0
	for i in range(len(num)):
		n = n * 10 % m
		n = (n + num[i]) % m
	rs = n
	y = 10 ** len(num) % m
	for i in range(len(num) - 1):
		n = (n * 10 - (y - 1) * num[i]) % m
		rs = (rs * y + n) % m
	print(rs)
	T -= 1


t = int(input())
decimal = [1]
mod = 10 ** 9 + 7
for i in range(10 ** 5 + 1):
	decimal.append(decimal[-1] * 10 % mod)

def num(n):
	ans = 0
	length = len(n)
	for i in range(0, length):
		ans += int(n[i]) * decimal[length - i - 1] % mod
	return ans
for i in range(0, t):
	n = input()
	length = len(n)
	p = 10 ** length % mod
	p1 = 10 ** (length - 1) % mod
	mul = [1]
	for j in range(0, length - 1):
		mul.append(mul[-1] * p % mod)
	value = num(n)
	ans = 0
	for j in range(length - 1, -1, -1):
		temp = value * mul[j] % mod
		ans += temp
		value = value - int(n[length - 1 - j]) * p1
		value = (value * 10 + int(n[length - 1 - j])) % mod
	print(ans % mod)


t = int(input())
modval = 10 ** 9 + 7
for _ in range(t):
	val = list(input())
	inp = 0
	res = 0
	multiplier = 1
	for i in val:
		inp = (inp * 10 + int(i)) % modval
		multiplier = multiplier * 10 % modval
	for i in val:
		res = (res * multiplier + inp) % modval
		inp = (inp * 10 - (multiplier - 1) * int(i)) % modval
	print(res)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	s = input()
	n = len(s)
	num = 0
	k = pow(10, n, mod)
	kk = pow(10, n - 1, mod)
	for i in range(n):
		num += pow(10, n - 1 - i, mod) * int(s[i])
		num %= mod
	ans1 = num
	for i in range(n - 1):
		ans = (num - kk * int(s[i])) * 10 % mod + int(s[i])
		ans1 = (ans1 * k + ans) % mod
		num = ans
	print(ans1 % mod)


MOD = 10 ** 9 + 7

def main():
	t = int(input())
	for i in range(t):
		s = list(map(int, input()))
		(p, m) = (0, 1)
		for d in reversed(s):
			p += d * m
			m = m * 10 % MOD
		r = 0
		for d in s:
			r = (r * m + p) % MOD
			p = (p * 10 - (m - 1) * d) % MOD
		print(r)
main()


a = 10 ** 9 + 7
for _ in range(int(input())):
	m = input()
	n = int(m)
	o = pow(10, len(m)) % a
	p = 0
	for i in m:
		i = int(i)
		p = (p * o + n) % a
		n = (n * 10 - (o - 1) * i) % a
	print(p)


t = int(input())
for _ in range(t):
	s = input()
	if len(s) == 1:
		print(s)
	else:
		mod = 10 ** 9 + 7
		l = len(s)
		curr = 0
		for i in s:
			curr *= 10
			curr += int(i)
			curr %= mod
		ans = curr
		p1 = 1
		p2 = 1
		for i in range(l):
			p1 *= 10
			p1 %= mod
		for i in range(l - 1):
			p2 *= 10
			p2 %= mod
		for i in range(l - 1):
			curr -= p2 * int(s[i]) % mod
			curr *= 10
			curr += int(s[i])
			curr %= mod
			ans *= p1
			ans %= mod
			ans += curr
			ans %= mod
		print(ans)


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
mod = 10 ** 9 + 7
for _ in range(int(input())):
	N = input()
	I = N
	l = len(N)
	N = int(N)
	Y = S = N
	e1 = 10 ** (l - 1) % mod
	e2 = e1 * 10 % mod
	for i in range(l - 1):
		k = int(I[i])
		S = ((S - k * e1) * 10 + k) % mod
		Y = (Y * e2 % mod + S) % mod
	print(Y % mod)


t = int(input())
mod = 10 ** 9 + 7
while t:
	t -= 1
	n = input()
	k = len(n)
	mul = [1]
	power = 10 ** k % mod
	power_1 = 10 ** (k - 1) % mod
	for i in range(k):
		temp = mul[-1] * power
		if temp >= mod:
			temp %= mod
		mul.append(temp)
	ans = 0
	val = int(n) % mod
	for i in range(k - 1, -1, -1):
		temp = val * mul[i]
		ans += temp
		if ans >= mod:
			ans %= mod
		val = val - int(n[k - 1 - i]) * power_1
		val = (val * 10 + int(n[k - 1 - i])) % mod
	print(ans % mod)


t = int(input())
for _ in range(t):
	mod = 10 ** 9 + 7
	n = input()
	ans = 0
	for i in n:
		ans = ans * 10 % mod
		ans += int(i)
		ans = ans % mod
	ini = 0
	main = [ans]
	while ini < len(n) - 1:
		current = main[-1]
		power = pow(10, len(n) - 1, mod)
		ans = (current - power * int(n[ini]) % mod) % mod
		ans = (ans * 10 + int(n[ini])) % mod
		main.append(ans)
		ini += 1
	power = pow(10, len(n), mod)
	final_ans = 0
	for i in range(len(main)):
		final_ans *= power
		final_ans = final_ans % mod
		final_ans += main[i]
		final_ans = final_ans % mod
	print(final_ans)


M = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	s = input()
	p = int(s)
	m = '1' + '0' * len(s)
	m = int(m) % M
	r = 0
	for d in s:
		d = int(d)
		r = (r * m + p) % M
		p = (p * 10 - (m - 1) * d) % M
	print(r)


for t in range(int(input())):
	s = input()
	t = 0
	mod = 10 ** 9 + 7
	n = len(s)
	d1 = {0: 0 for i in range(len(s))}
	d2 = {0: 0 for i in range(len(s))}
	pow = 1
	mu = 1
	for i in range(1, len(s)):
		d1[i] = d1[i - 1] * 10 % mod + int(s[i - 1])
		pow = pow * 10 % mod
	c = 0
	for i in reversed(range(len(s))):
		d2[i] = (int(s[i]) * mu % mod + c % mod) % mod
		c = d2[i]
		mu = mu * 10 % mod
	mu = 1
	for i in range(len(s)):
		t = (t * pow * 10 % mod + d2[i] * mu % mod + d1[i] % mod) % mod
		mu = mu * 10 % mod
	print(t)


MOD = 10 ** 9 + 7
INF = float('+inf')

def si():
	return str(stdin.readline())

def ii():
	return int(raw_input())

def mi():
	return map(int, raw_input().split())

def li():
	return [int(i) for i in raw_input().split()]

def debug(x):
	return stdout.write(str(x))

def limul(list):
	return eval('*'.join((str(item) for item in list)))

def main():
	t = int(input())
	for i in range(t):
		s = list(map(int, input()))
		(p, m) = (0, 1)
		for d in reversed(s):
			p += d * m
			m = m * 10 % MOD
		r = 0
		for d in s:
			r = (r * m + p) % MOD
			p = (p * 10 - (m - 1) * d) % MOD
		print(r)
main()


from math import *
MOD = 1000000007
t = int(input())
for f in range(t):
	s = input()
	t_y = 0
	y = 0
	pow = 1
	n = len(s)
	for i in range(n):
		t_y = (t_y * 10 % MOD + int(s[i])) % MOD
		if i:
			pow = pow * 10 % MOD
	y = t_y
	for i in range(n - 1):
		t_y = (t_y - pow * int(s[i]) % MOD % MOD) % MOD
		if t_y < 0:
			t_y += MOD
		t_y = (t_y * 10 % MOD + int(s[i])) % MOD
		y = (y * (pow * 10) % MOD % MOD + t_y) % MOD
	print(y)


def modulo(s, x):
	y = 0
	l = len(s)
	for i in range(0, l):
		y = (y * 10 + ord(s[i]) - 48) % x
	return y
for _ in range(int(input())):
	s = input()
	l = len(s)
	x = 1
	for i in range(1, l):
		x = x * 10 % 1000000007
	result = modulo(s, 1000000007)
	res = result
	for i in range(0, l - 1):
		result = ((result - (ord(s[i]) - 48) * x) * 10 + (ord(s[i]) - 48)) % 1000000007
		res = (res * x * 10 + result) % 1000000007
	print(res % 1000000007)


M = 10 ** 9 + 7
N = 100001
p10 = [None] * N
k = 1
for i in range(N):
	p10[i] = k
	k = k * 10 % M
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	if n == 1:
		print(s)
	else:
		s = s[-2::-1] + s[-1]
		m = p10[n - 1]
		pm = [None] * (n + 2)
		k = 1
		for i in range(n + 2):
			pm[i] = k
			k = k * m % M
		r = sum((d * (p10[i] * (pm[i + 1] - 1) + pm[i + 2] * p10[i + 1] * (pm[n - i - 1] - 1)) for (i, d) in enumerate(map(int, s))))
		im = pow(m - 1, M - 2, M)
		print(im * r % M)


m = 10 ** 9 + 7
powers_of_10_mod_m = [None for _ in range(10 ** 5 + 1)]

def precompute_10_power_n_mod_m():
	powers_of_10_mod_m[0] = 1
	for i in range(1, 10 ** 5 + 1):
		powers_of_10_mod_m[i] = 10 * powers_of_10_mod_m[i - 1] % m
T = int(input())
precompute_10_power_n_mod_m()
while T:
	N = input()
	mod_N = len(N)
	int_N = int(N)
	N_mod_m = 0
	for i in range(mod_N):
		temp = int(N[i]) * powers_of_10_mod_m[mod_N - (i + 1)] % m
		N_mod_m = (N_mod_m + temp) % m
	Y_N = N_mod_m * pow(powers_of_10_mod_m[mod_N], mod_N - 1, m)
	curr_N_mod_m = N_mod_m
	for i in range(mod_N - 1):
		temp1 = int(N[i]) * powers_of_10_mod_m[mod_N - 1] % m
		temp2 = (curr_N_mod_m - temp1) % m
		temp3 = temp2 * 10 % m
		temp4 = (temp3 + int(N[i])) % m
		curr_N_mod_m = temp4
		Y_N = (Y_N + curr_N_mod_m * pow(powers_of_10_mod_m[mod_N], mod_N - (i + 2), m) % m) % m
	print(Y_N)
	T -= 1


def mody(num, a):
	res = 0
	for i in range(0, len(num)):
		res = (res * 10 + int(num[i])) % a
	return res
t = int(input())
mod = 10 ** 9 + 7
while t:
	t -= 1
	n = input()
	k = len(n)
	mul = [1]
	powe = 10 ** k % mod
	pew = 10 ** (k - 1) % mod
	for i in range(k):
		temp = mul[-1] * powe
		if temp >= mod:
			temp %= mod
		mul.append(temp)
	flag = k < 10
	ans = 0
	val = mody(n, mod)
	for i in range(k - 1, -1, -1):
		temp = val * mul[i]
		if temp >= mod:
			temp %= mod
		ans += temp
		if ans >= mod:
			ans %= mod
		val = val - int(n[k - 1 - i]) * pew
		val = (val * 10 + int(n[k - 1 - i])) % mod
	print(ans % mod)


t = int(input())
mod = 10 ** 9 + 7
for i in range(t):
	n = input()
	l = len(n)
	power10 = [None for j in range(l + 1)]
	power10[0] = 1
	prod = 1
	for j in range(1, l + 1):
		prod = prod * 10
		if prod >= mod:
			prod %= mod
		power10[j] = prod
	front = [None for j in range(l)]
	end = [None for j in range(l)]
	num = [None for j in range(l)]
	end[0] = 0
	front[l - 1] = int(n[l - 1])
	for j in range(1, l):
		end[j] = (end[j - 1] * 10 % mod + int(n[j - 1])) % mod
	for j in range(l - 2, -1, -1):
		front[j] = (int(n[j]) * power10[l - j - 1] % mod + int(front[j + 1])) % mod
	for j in range(l):
		num[j] = (front[j] * power10[j] % mod + end[j]) % mod
	ans = 0
	for j in range(l):
		ans = (ans * power10[l] % mod + num[j]) % mod
	print(ans)


M = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	s = list(map(ord, input()))
	(p, m) = (0, 1)
	for i in range(len(s) - 1, -1, -1):
		s[i] -= 48
		p += s[i] * m
		m = m * 10 % M
	r = 0
	for d in s:
		r = (r * m + p) % M
		p = (p * 10 - (m - 1) * d) % M
	print(r)