Eugene has to do his homework. But today, he is feeling very lazy and wants to you do his homework. His homework has the following given maths problem.
You are given three integers: A, N, M. You write the number A appended to itself N times in a row. Let's call the resulting big number X. For example, if A = 120, N = 3, then X will be 120120120. Find out the value of X modulo M.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follow.
Each test case is described in one line containing three integers: A, N and M as described in the problem statement.

-----Output-----
For each test case, output a single line containing an integer denoting the value of X modulo M.

-----Constraints-----
- 1 ≤ T ≤ 105
- 0 ≤ A ≤ 109
- 1 ≤ N ≤ 1012
- 2 ≤ M ≤ 109

-----Subtasks-----
Subtask #1 (15 points):
- 0 ≤ A ≤ 100
- 1 ≤ N ≤ 105

Subtask #2 (25 points):
- 1 ≤ N ≤ 109

Subtask #3 (60 points):
- Original constraints

-----Example-----
Input:
2
12 2 17
523 3 11

Output:
5
6

-----Explanation-----
Example 1: As A = 12, N = 2, X = 1212, 1212 modulo 17 = 5
Example 2. As A = 523, N = 3, X = 523523523, 523523523 modulo 11 = 6

Difficulty: HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	(a, n, m) = map(int, input().split(' '))
	s = len(str(a))
	c = 10 ** s - 1
	w = c * m
	b = pow(10, n * s, w) - 1
	d = b // c
	ans = d % m * (a % m)
	print(ans % m)


m = int(1000000000.0) + 7

def mul(a, b):
	c0 = a[0] * b[0] + a[1] * b[2]
	c1 = a[0] * b[1] + a[1] * b[3]
	c2 = a[2] * b[0] + a[3] * b[2]
	c3 = a[2] * b[1] + a[3] * b[3]
	if c0 < 0 or c0 >= m:
		c0 %= m
	if c1 < 0 or c1 >= m:
		c1 %= m
	if c2 < 0 or c2 >= m:
		c2 %= m
	if c3 < 0 or c3 >= m:
		c3 %= m
	return (c0, c1, c2, c3)

def matpow(mat, n):
	res = (1, 0, 0, 1)
	while n:
		if n & 1:
			res = mul(res, mat)
		mat = mul(mat, mat)
		n >>= 1
	return res

def solve(a, n, m):
	p = 1
	while p <= a:
		p *= 10
	p %= m
	tran = (p + 1, -p, 1, 0)
	ptran = matpow(tran, n - 1)
	f = (ptran[2] * (p + 1) + ptran[3]) % m
	res = f * a % m
	return res % m
for t in range(int(input())):
	(a, n, m) = map(int, input().split())
	res = solve(a, n, m)
	print(res)


import math

def findout(A, N, M):
	p = int(math.log(A, 10))
	R = pow(10, p + 1, M)

	def largesum(x, N, M):
		if N == 0:
			return 1
		elif N == 1:
			return (1 + x) % M
		elif N == 2:
			return (1 + x + x ** 2) % M
		elif N == 3:
			return (1 + x + x ** 2 + x ** 3) % M
		if N % 2 == 1:
			k = N // 2
			temp = pow(x, k + 1, M)
			ans = largesum(x, k, M)
			ans = ans + temp * ans
			ans %= M
			return ans
		else:
			k = N // 2
			ans = largesum(x, k - 1, M)
			ans = 1 + x * ans + pow(x, k + 1, M) * ans
			ans %= M
			return ans
	ans = largesum(R, N - 1, M) * A % M
	return ans
T = int(input())
for _ in range(T):
	(A, N, M) = list(map(int, input().strip().split(' ')))
	if A == 0:
		print(0)
	else:
		print(findout(A, N, M))


def modulo_big_num(x, n, m):
	x_mod_m = x % m
	if n == 1:
		return (x_mod_m, 1)
	(x_raised_to_n_by_2, value_at_n_by_2) = modulo_big_num(x, n // 2, m)
	value_at_n = value_at_n_by_2 % m * (x_raised_to_n_by_2 + 1) % m % m
	x_raised_to_n = x_raised_to_n_by_2 * x_raised_to_n_by_2 % m
	if n % 2:
		value_at_n = (1 + x_mod_m * value_at_n % m) % m
		x_raised_to_n = x_mod_m * x_raised_to_n % m
	return (x_raised_to_n, value_at_n)

def start():
	num_test_cases = input()
	for i in range(int(num_test_cases)):
		(a, n, m) = input().split()
		if a == '0':
			print(0)
		else:
			nda = len(str(a))
			m = int(m)
			a = int(a)
			n = int(n)
			x = 10 ** nda
			(_, result) = modulo_big_num(x, n, m)
			print(a % m * result % m)
start()


for _ in range(int(input())):
	(a, n, m) = map(int, input().split(' '))
	print((pow(10, n * len(str(a)), (10 ** len(str(a)) - 1) * m) - 1) // (10 ** len(str(a)) - 1) % m * (a % m) % m)


import math

def bigmod(a, p, m):
	r = 1
	while p > 0:
		if p % 2 == 1:
			r = r * a % m
		p //= 2
		a = a * a % m
	return r
T = int(input())
for t in range(T):
	(A, N, M) = map(int, input().split())
	if A == 0:
		print(0)
		continue
	digit = len(str(A))
	power_of_ten = 10 ** digit
	m = M * (power_of_ten - 1)
	Sum = bigmod(power_of_ten, N, m)
	Sum //= power_of_ten - 1
	Sum = Sum * A % M % M
	print(Sum)


t = int(input())
ans = []
exponents = []

def calc_exponents(x, e, m):
	if e == 0:
		exponents.append(1)
		return 1
	if e % 2 == 0:
		prod = calc_exponents(x, e // 2, m)
		temp = prod % m * prod % m % m
	else:
		prod = calc_exponents(x, (e - 1) // 2, m)
		temp = prod % m * prod % m % m * x % m % m
	exponents.append(temp)
	return temp

def gp_sum(n, r, m, pt):
	if n == 1:
		return 1
	if n % 2 == 0:
		sn = (1 + exponents[pt]) % m * gp_sum(n // 2, r, m, pt - 1) % m
	else:
		sn = (1 + exponents[pt]) % m * gp_sum((n - 1) // 2, r, m, pt - 1) % m + exponents[pt] % m * exponents[pt] % m % m
	return sn
for i in range(t):
	(a, n, m) = list(map(int, input().split()))
	length = len(str(a))
	r = pow(10, length)
	exponents = []
	calc_exponents(r, n, m)
	sum_part = gp_sum(n, r, m, len(exponents) - 2)
	total_prod = a % m * sum_part % m
	ans.append(total_prod)
for x in ans:
	print(x)


def calculateRecursive(xmodM, m, n):
	if n == 1:
		ans = []
		ans.append(int(1))
		ans.append(int(1))
		return ans
	if n % 2 == 1:
		result = calculateRecursive(xmodM, m, n // 2)
		temp = xmodM * result[0] % m
		temp1 = temp * xmodM % m
		temp2 = temp1 * result[1] % m
		ans = []
		ans.append(temp ** 2 % m)
		ans.append((temp + temp2 + result[1]) % m)
		return ans
	else:
		result = calculateRecursive(xmodM, m, n / 2)
		temp = xmodM * result[0] % m
		temp1 = temp * result[1] % m
		ans = []
		ans.append(result[0] * temp % m)
		ans.append((result[1] + temp1) % m)
		return ans
	return a
numofcases = int(input())
for i in range(numofcases):
	(a, n, m) = input().split(' ')
	intNumOfDigits = len(a)
	a = int(a)
	n = int(n)
	m = int(m)
	AmodM = int(a % m)
	x = 10 ** intNumOfDigits
	xmodM = x % m
	lngRem = int(1)
	lngPrevRem = 1
	ans = calculateRecursive(xmodM, m, n)
	print(int(ans[1]) * AmodM % m)


def findMod(a, n, m):
	mf = 10 ** len(str(a)) % m
	ans = 0
	while n:
		if n % 2 == 1:
			ans = (ans * mf % m + a % m) % m
		a = (a * mf % m + a) % m
		mf = pow(mf, 2, m)
		n = n // 2
	return ans
for _ in range(int(input())):
	(a, n, m) = [int(i) for i in input().split()]
	print(findMod(a, n, m))


A = 0
N = 9
M = 9
p = 9
leng = 0

def fm(left):
	if left == 1:
		return int(p % M)
	half = left // 2
	par = fm(half) % M
	join = (par + pow(10, int(leng * half), M) * par) % M
	if left % 2:
		join = (join * p + p) % M
	return int(join)
for _ in range(int(input())):
	(A, N, M) = map(int, input().split())
	leng = len(str(A))
	p = pow(10, leng, M)
	if N == 1:
		print(A % M)
		continue
	ans = A % M
	ans = ans * (fm(N - 1) + 1) % M
	print(ans)


t = int(input())

def ans(a, n, m):
	if n is 1:
		return a % m
	h = ans(a, n // 2, m)
	l = len(str(a))
	res = (h + h * pow(10, n // 2 * l, m)) % m
	if n & 1 is 1:
		res += a * pow(10, (n - 1) * l, m) % m
		res %= m
	return res
for _ in range(t):
	(a, n, m) = list(map(int, input().split()))
	print(ans(a, n, m))


import math

def no(n):
	c = 0
	while n > 0:
		c += 1
		n //= 10
	return c

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
for _ in range(int(input())):
	(a, n, m) = map(int, input().split(' '))
	s = len(str(a))
	c = 10 ** s - 1
	w = c * m
	b = pow(10, n * s, w) - 1
	d = b // c
	ans = d % m * (a % m)
	print(ans % m)


import sys

def cal_power(a, n, m):
	if n == 0:
		return 1
	elif n == 1:
		return a % m
	elif not n % 2:
		return (cal_power(a, n // 2, m) % m) ** 2 % m
	else:
		return a % m * (cal_power(a, (n - 1) // 2, m) % m) ** 2 % m % m

def cal(b, n, m):
	if n == 0:
		return 0
	elif n == 1:
		return b % m
	elif not n % 2:
		return (1 + cal_power(b, n // 2, m)) % m * (cal(b, n // 2, m) % m) % m
	else:
		return ((1 + cal_power(b, (n + 1) // 2, m)) % m * (cal(b, (n - 1) // 2, m) % m) + cal_power(b, (n + 1) // 2, m) % m) % m

def solve(a, n, m):
	l = len(str(a))
	x = a % m
	q = 10 ** l % m
	return x * (1 + cal(q, n - 1, m)) % m
for _ in range(int(input())):
	(a, n, m) = [int(temp) for temp in input().split()]
	print(solve(a, n, m))


import math

def modpow(a, b, m):
	res = 1
	while b > 0:
		if b % 2 is 1:
			res = res * a % m
		a = a % m * (a % m) % m
		b = b // 2
	return res % m

def digits(x):
	l = 0
	if x == 0:
		return 1
	while x:
		x = x // 10
		l += 1
	return l

def solve(a, n, mod):
	l = digits(a)
	pow_ = math.ceil(pow(10, l)) - 1
	newmod = mod * pow_
	temp = modpow(10, l * n, newmod)
	temp2 = a * (temp - 1) % newmod
	temp2 = temp2 // pow_
	return temp2 % mod

def main():
	t = int(input())
	while t > 0:
		(a, n, mod) = map(int, input().split())
		res = solve(a, n, mod)
		print(res)
		t = t - 1
main()


def CALC(a, p, m):
	if p == 0:
		return 1
	if p == 1:
		return a % m
	temp = CALC(a, int(p / 2), m)
	if p % 2 != 0:
		return temp % m * (temp % m) % m * (a % m) % m
	return temp % m * (temp % m) % m
t = int(input())
for i in range(1, t + 1):
	(a, n, m) = map(int, input().split(' '))
	save = a
	r = 1
	if a == 0:
		print(0)
	else:
		while a > 0:
			a = int(a / 10)
			r = r * 10
		ans = save % m
		M = m * (r - 1)
		mult = CALC(r, n, M) - 1 + M
		mult = mult % M
		mult = int(mult / (r - 1))
		ans = ans * mult % m
		print(int(ans))


def foo(a, n, m):
	t = 1
	s = 0
	while n > 0:
		if n & 1 == 1:
			s = (a * s + t) % m
		n >>= 1
		t = (a + 1) * t % m
		a = a * a % m
	return s
T = int(input())
for t in range(T):
	(A, N, M) = map(int, input().strip().split())
	if A == 0:
		ans = 0
	elif N == 1:
		ans = A % M
	else:
		ans = A % M * foo(pow(10, len(str(A)), M), N, M) % M
	print(ans)


for _ in range(int(input())):
	(a, n, m) = [int(x) for x in input().split()]
	d = len(str(a))
	ans = 0
	p10 = pow(10, d, m)
	aa = a % m
	p2 = 1
	while True:
		if n & p2 != 0:
			ans = (ans * p10 + aa) % m
			n -= p2
		if n == 0:
			break
		p2 *= 2
		aa = aa * (p10 + 1) % m
		p10 = p10 * p10 % m
	print(ans)


from math import log10

def geo_sum_mod(r, n, m):
	if n == 0:
		return 1
	if n % 2 == 1:
		return (1 + r) * geo_sum_mod(r * r % m, (n - 1) // 2, m) % m
	return (1 + r * ((1 + r) * geo_sum_mod(r * r % m, n // 2 - 1, m)) % m) % m

def main():
	T = int(input())
	for _ in range(T):
		(A, N, M) = map(int, input().split())
		if A == 0:
			print(0)
		else:
			print(A * geo_sum_mod(pow(10, int(log10(A)) + 1, M), N - 1, M) % M)
main()


def f(x, n, m):
	res = 1
	if n > 1:
		res = f(x, n // 2, m) * (1 + pow(x, n // 2, m)) % m
		if n % 2:
			res = (res * x + 1) % m
	return res
t = int(input())
for it in range(t):
	words = input().split()
	(a, n, m) = [int(x) for x in words]
	l = len(words[0])
	x = pow(10, l, m)
	res = f(x, n, m) * a % m
	print(res)


def modexp(a, n, mod):
	r = 1
	a = a % mod
	while n > 0:
		if n & 1 == 1:
			r = r * a % mod
		n = n >> 1
		a = a * a % mod
	return r
ttt = int(input())
while ttt > 0:
	ttt -= 1
	l = input()
	(aa, bb, cc) = l.split(' ')
	a = int(aa)
	b = int(bb)
	c = int(cc)
	p = len(aa)
	k = 1
	for i in range(1, p + 1):
		k = k * 10
	zz = (k - 1) * c
	k1 = modexp(k, b, zz)
	k -= 1
	k1 = k1 * a % zz
	k1 -= a
	if k1 < 0:
		k1 = zz - k1
	p = k1 // k
	print(p)