There is a strange game played in ChefLand. 

The game starts with N white balls, the i-th of which has a power of S_{i}. It is known that 0 ≤ S_{i} ≤ 9. On each level, a black ball with power K hits each of the white balls. After the collision, the power of each white ball is multiplied by K. 

However, white balls are only allowed to have single-digit power. In order to maintain this, a white ball whose power contains multiple digits splits into several white balls with single-digit power, one per digit.

For example, consider a white ball with a power of 4.
If K = 2, its resulting power is 8 and it remains a single ball.
If K = 13, its resulting power is 52, so it splits into two white balls with power 5 and 2 respectively.
If K = 27, its resulting power is 108, so it splits into three white balls with power 1, 0, and 8 respectively.

The aim of the game is to determine the number of white balls after M levels. Note that K remains the same for every level.

Please help Chef win the game. Since the answer can be large, print it modulo 10^{9} + 7.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains three space-separated integers N, K, and M.
- The second line of each test case contains a string S of length N, where S_{i} is the initial power of i-th ball.

------ Output Format ------ 

For each test case, output in a single line the number of white balls at the end of the game, modulo 10^{9} + 7.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 1000$
$0 ≤ K,M ≤ 10^{9}$

------ subtasks ------ 

Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
3
4 9 2
5418
5 63 3
40514
1 100000 100000
0
----- Sample Output 1 ------ 
14
88
1

----- explanation 1 ------ 
Test case $1$:
- Initially $S = 5418$
- After the $1^{st}$, level $S = 4536972$
- After the $2^{nd}$ level, $S = 36452754816318$

There are $14$ white balls, so the answer is $14$.

Test case $3$: After each level, $S = 0$. So, the answer is $1$.

Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
import collections
import math
mod = 1000000007

def multiply(a, b):
	mul = [[0] * 10 for _ in range(10)]
	for i in range(10):
		for j in range(10):
			for k in range(10):
				mul[i][j] += a[i][k] * b[k][j]
				mul[i][j] %= mod
	return mul
t = int(input())
for _ in range(t):
	(n, k, m) = map(int, input().split())
	s = str(input())
	matrix_A = [0] * 10
	for x in s:
		matrix_A[ord(x) - ord('0')] += 1
	matrix_C = [[0] * 10 for _ in range(10)]
	for i in range(10):
		for j in range(10):
			cur = str(j * k)
			matrix_C[i][j] += cur.count(str(i))
	matrix_E = [[0] * 10 for _ in range(10)]
	for i in range(10):
		matrix_E[i][i] = 1
	while m != 0:
		if m % 2 == 1:
			matrix_E = multiply(matrix_E, matrix_C)
			m -= 1
		matrix_C = multiply(matrix_C, matrix_C)
		m //= 2
	matrix_B = [0] * 10
	for i in range(10):
		for j in range(10):
			matrix_B[i] += matrix_A[j] * matrix_E[i][j]
			matrix_B[i] %= mod
	print(sum(matrix_B) % mod)


import numpy as np
nmax = 1000000007
t = int(input())
for i in range(t):
	mat = np.zeros((10, 10))
	mat = mat.astype(int)
	(n, k, m) = map(int, input().split())
	if m == 0:
		print(n)
		input()
		continue
	for j in range(10):
		for v in map(int, list(str(j * k))):
			mat[v, j] += 1
	mats = [mat]
	for j in range(int(np.log2(m))):
		mat = mat @ mat % nmax
		mats.append(mat)
	fmat = np.identity(10)
	fmat = fmat.astype(int)
	j = 0
	while m > 0:
		if m % 2 == 1:
			fmat = fmat @ mats[j] % nmax
		m = m // 2
		j += 1
	vec = np.zeros((10, 1))
	vec = vec.astype(int)
	for v in map(int, list(input())):
		vec[v, 0] += 1
	outvec = fmat @ vec % nmax
	print(sum(sum(outvec) % nmax))


import math, bisect, heapq, random, sys, itertools
input = sys.stdin.readline
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p2 = [1]
for i in range(70):
	p2.append(p2[-1] * 2)
p = 10 ** 9 + 7
ANS = []

def mul(X, Y):
	result = [[0 for j in range(len(Y[0]))] for i in range(len(X))]
	for i in range(len(X)):
		for j in range(len(Y[0])):
			for k in range(len(Y)):
				result[i][j] = (result[i][j] + X[i][k] * Y[k][j]) % p
	return result

def mat_exp(A, n):
	res = [[0 for i in range(10)] for j in range(10)]
	for i in range(10):
		res[i][i] = 1
	while n:
		if n % 2:
			res = mul(A, res)
		n //= 2
		A = mul(A, A)
	return res
for t in range(int(input())):
	(n, k, m) = ints()
	a = [int(i) for i in input().strip()]
	A = [[0 for i in range(10)] for j in range(10)]
	for i in range(10):
		x = str(i * k)
		x = [int(j) for j in x]
		for j in x:
			A[j][i] += 1
	A = mat_exp(A, m)
	r = [[0] for i in range(10)]
	for i in a:
		r[i][0] += 1
	ans = mul(A, r)
	print(sum((sum(i) for i in ans)) % p)


def PROBLEM():
	for _ in range(int(input())):
		ins = list(map(int, input().split()))
		n = ins[0]
		k = ins[1]
		t = ins[2]
		m = 10 ** 9 + 7
		init_num = input()
		A = [None] * 10
		for i in range(10):
			A[i] = [0] * 10
		for i in range(10):
			v = str_to_vector(str(i * k))
			for j in range(10):
				A[j][i] = v[j]
		Am = matpow(A, t, m)
		init_vec = str_to_vector(init_num)
		final_vec = [0] * 10
		for i in range(10):
			for j in range(10):
				final_vec[i] += Am[i][j] * init_vec[j] % m
		final_sum = 0
		for i in range(10):
			final_sum = (final_sum + final_vec[i]) % m
		print(final_sum)

def str_to_vector(s):
	res = [0] * 10
	for i in range(0, len(s)):
		idx = int(s[i])
		res[idx] = res[idx] + 1
	return res

def matmul(A, B, m):
	n = len(A)
	res = [None] * n
	for i in range(n):
		res[i] = [0] * n
	for i in range(n):
		for j in range(n):
			for k in range(n):
				res[i][j] += A[i][k] * B[k][j] % m
	return res

def identity(n):
	res = [None] * n
	for i in range(n):
		res[i] = [0] * n
		res[i][i] = 1
	return res

def matpow(A, k, m):
	n = len(A)
	if k == 0:
		return identity(n)
	p = matpow(A, k // 2, m)
	p = matmul(p, p, m)
	if k % 2 == 0:
		return p
	else:
		return matmul(p, A, m)
PROBLEM()


def multiply(A, B, N):
	result = [[0 for i in range(N)] for i in range(N)]
	for i in range(N):
		for j in range(N):
			for k in range(N):
				result[i][j] += A[i][k] * B[k][j]
				result[i][j] %= MOD
	return result

def power(A, N):
	ans = [[0 for i in range(10)] for i in range(10)]
	for i in range(10):
		ans[i][i] = 1
	while N:
		if N & 1:
			ans = multiply(ans, A, 10)
		N >>= 1
		A = multiply(A, A, 10)
	return ans

def preprocess(F, K):
	for i in range(10):
		for j in range(10):
			x = i * K
			if x == 0 and x == j:
				F[i][j] += 1
				continue
			while x > 0:
				if x % 10 == j:
					F[i][j] += 1
				x //= 10
t = int(input())
while t:
	(n, k, m) = map(int, input().split(' '))
	s = input()
	F = [[0 for i in range(10)] for i in range(10)]
	preprocess(F, k)
	cnt = [0 for i in range(10)]
	for i in s:
		cnt[int(i)] += 1
	(count, MOD) = (0, 10 ** 9 + 7)
	matrix = power(F, m)
	for i in range(10):
		for j in range(10):
			count += cnt[i] * matrix[i][j]
			count %= MOD
	print(count)
	t -= 1


def compute(st, k, m):
	di = {i: [str(i * k).count(str(j)) for j in range(10)] for i in range(10)}
	cach = [[int(i == j) for i in range(10)] for j in range(10)]
	temp = [[0 for i in range(10)] for j in range(10)]
	for i in range(10):
		for j in range(10):
			for k in range(10):
				temp[i][k] = (temp[i][k] + cach[i][j] * di[j][k]) % (10 ** 9 + 7)
	cach = temp[:][:]
	s = [0 for i in range(10)]
	for e in st:
		s[int(e)] += 1
	while m > 0:
		if m % 2 == 1:
			temps = [0 for i in range(10)]
			for i in range(10):
				for j in range(10):
					temps[j] = (temps[j] + s[i] * cach[i][j]) % (10 ** 9 + 7)
			s = temps[:]
		temp = [[0 for i in range(10)] for j in range(10)]
		for i in range(10):
			for j in range(10):
				for k in range(10):
					temp[i][k] = (temp[i][k] + cach[i][j] * cach[j][k]) % (10 ** 9 + 7)
		cach = temp[:][:]
		m = m // 2
	return sum(s) % (10 ** 9 + 7)
t = int(input())
for i in range(t):
	inp1 = input()
	inp1 = inp1.split(' ')
	inp1 = [int(inp1[i]) for i in range(len(inp1))]
	inp2 = input()
	print(compute(inp2, inp1[1], inp1[2]))


MOD = 10 ** 9 + 7

class ModuloMatrix:

	def __init__(self, N=10, ident=False, K=None):
		self.N = N
		self.values = [[0] * N for _ in range(N)]
		if ident:
			for i in range(N):
				self.values[i][i] = 1
		elif K is not None:
			for j in range(N):
				SK = str(j * K)
				for i in range(N):
					self.values[i][j] += SK.count(str(i))

	def __mul__(self, M):
		R = ModuloMatrix(self.N)
		for i in range(self.N):
			for j in range(self.N):
				for k in range(self.N):
					R.values[i][j] = (R.values[i][j] + self.values[i][k] * M.values[k][j]) % MOD
		return R

	def __pow__(self, P):
		R = ModuloMatrix(self.N, ident=True)
		while P:
			if P % 2:
				R = R * self
			self = self * self
			P >>= 1
		return R

	def dot(self, V):
		R = [[0] for _ in range(self.N)]
		for i in range(self.N):
			j = 0
			for k in range(self.N):
				R[i][j] = (R[i][j] + self.values[i][k] * V[k][j]) % MOD
		return R

	def __str__(self):
		txt = ''
		for i in range(self.N):
			txt += i and '\n' or ''
			for j in range(self.N):
				txt += (j and ' ' or '') + str(self.values[i][j])
		return txt

def naive(N, K, M, S):
	E = [[0] for _ in range(10)]
	for s in S:
		E[int(s)][0] += 1
	mat = ModuloMatrix(K=K)
	mat = mat ** M
	E = mat.dot(E)
	return sum((e[0] for e in E)) % MOD
T = int(input().strip())
for _ in range(T):
	(N, K, M) = [int(x) for x in input().strip().split()[:3]]
	S = input().strip()[:N]
	print(naive(N, K, M, S))


from typing import List
MODULO = 10 ** 9 + 7

def multiply_matmat(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
	return [[sum((a * b % MODULO for (a, b) in zip(A[r], [row[c] for row in B]))) % MODULO for c in range(10)] for r in range(10)]

def multiply_matvec(A: List[List[int]], v: List[int]) -> List[int]:
	return [sum((a * b % MODULO for (a, b) in zip(A[r], v))) % MODULO for r in range(10)]

def power_mat(A: List[List[int]], exp: int) -> List[List[int]]:
	if exp == 1:
		return A
	elif exp % 2 == 0:
		return power_mat(multiply_matmat(A, A), exp // 2)
	else:
		return multiply_matmat(A, power_mat(multiply_matmat(A, A), exp // 2))

def solve(t):
	(N, K, M) = map(int, input().split())
	S = input().strip()
	P = [S.count(str(i)) for i in range(10)]
	A = [[0 for j in range(10)] for i in range(10)]
	for p in range(10):
		new_balls = '%d' % (p * K)
		for new_p in map(int, new_balls):
			A[new_p][p] += 1
	if M > 0:
		P = multiply_matvec(power_mat(A, M), P)
	print(sum(P) % MODULO)
T = int(input())
for t in range(T):
	solve(t + 1)


from sys import stdin
input = stdin.readline
MODULO = 10 ** 9 + 7

def matvectormultiply(a, b, m):
	c = [0] * m
	for i in range(m):
		for j in range(m):
			c[i] = (c[i] + a[i][j] * b[j]) % MODULO
	return c

def matmultiply(a, b, m):
	c = [[0] * m for i in range(m)]
	for i in range(m):
		for j in range(m):
			for k in range(m):
				c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MODULO
	return c

def matadd(a, b, m):
	c = [[0] * m for i in range(m)]
	for i in range(m):
		for j in range(m):
			c[i][j] = (a[i][j] + b[i][j]) % MODULO
	return c

def matpower(a, n, m):
	answer = [[1 if i == j else 0 for i in range(m)] for j in range(m)]
	while n > 0:
		if n % 2 == 1:
			answer = matmultiply(answer, a, m)
		a = matmultiply(a, a, m)
		n = n // 2
	return answer

def solve(N, K, M, S):
	balls = [0] * 10
	for s in S:
		balls[int(s)] += 1
	black = [[0] * 10 for i in range(10)]
	for i in range(10):
		for s in str(i * K):
			black[int(s)][i] += 1
	black = matpower(black, M, 10)
	return sum(matvectormultiply(black, balls, 10)) % MODULO
T = int(input().strip())
for problem in range(1, T + 1):
	(N, K, M) = [int(x) for x in input().strip().split()]
	S = input().strip()
	print(solve(N, K, M, S))


p = 10 ** 9 + 7

def get_s_v(s):
	l = [0 for i in range(10)]
	for e in s:
		l[int(e)] += 1
	return l

def get_m(k):
	l = [[0 for i in range(10)] for j in range(10)]
	for i in range(10):
		v = get_s_v(str(i * k))
		for j in range(10):
			l[j][i] = v[j]
	return l

def get_p(m):
	l = list()
	while m > 0:
		l.append(m % 2)
		m = m // 2
	return l

def sq(X):
	Y = list()
	for i in range(10):
		Y.append([])
		for j in range(10):
			r = 0
			for k in range(10):
				r += X[i][k] * X[k][j] % p
			Y[i].append(r)
	return Y

def get_p_of_m(A, n):
	l = [A]
	i = 0
	B = list(A)
	while i < n:
		B = sq(B)
		l.append(B)
		i += 1
	return l

def mul(A, v):
	w = list()
	for i in range(len(v)):
		r = 0
		for j in range(len(v)):
			r += A[i][j] * v[j] % p
		w.append(r)
	return w

def get_res(pa, po, q):
	for i in range(len(pa)):
		if pa[i] == 1:
			q = mul(po[i], q)
	return q
for i in range(int(input())):
	(n, k, m) = map(int, input().split())
	s = input()
	q_0 = get_s_v(s)
	A = get_m(k)
	parts = get_p(m)
	powers = get_p_of_m(A, len(parts))
	print(sum(get_res(parts, powers, q_0)) % p)


Mod = 10 ** 9 + 7
t = int(input())
for tt in range(t):
	K100X = [[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]], [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]]
	a = list(map(int, input().split()))
	n = a[0]
	k = a[1]
	m = a[2]
	M = str(m)
	l = list(map(int, input()))
	Lcalu = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	for firstput_i in range(n):
		Lcalu[l[firstput_i]] += 1
	for kmaker_i in range(10):
		for kmaker_j in list(map(int, str(kmaker_i * k))):
			K100X[0][kmaker_j][kmaker_i] += 1
	for kmaker_h in range(1, 10):
		if m < 10 ** kmaker_h:
			break
		for kmaker_i in range(10):
			Lkmaker = [0] * 10
			Lkmaker[kmaker_i] = 1
			Lkmaker = tuple(Lkmaker)
			for kmaker_j in range(10):
				lkmaker = [0] * 10
				for kmaker_k in range(10):
					for kmaker_l in range(10):
						lkmaker[kmaker_k] += K100X[kmaker_h - 1][kmaker_k][kmaker_l] * Lkmaker[kmaker_l]
				Lkmaker = tuple(lkmaker)
			for kmaker_final in range(10):
				K100X[kmaker_h][kmaker_final][kmaker_i] += Lkmaker[kmaker_final] % Mod
	for calu_i in range(len(M)):
		LLcalu = tuple(Lcalu)
		for calu_i5 in range(int(M[(calu_i + 1) * -1])):
			lcalu = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
			for calu_j in range(10):
				for calu_k in range(10):
					lcalu[calu_j] += K100X[calu_i][calu_j][calu_k] * LLcalu[calu_k]
			LLcalu = tuple(lcalu)
		for y_i in range(10):
			Lcalu[y_i] = LLcalu[y_i] % Mod
	FINALAns = 0
	for z_i in range(10):
		FINALAns += Lcalu[z_i]
	print(FINALAns % Mod)


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7

def DFS(num_steps_left, ball_counts):
	if num_steps_left == 0:
		return ball_counts
	for i in range(len(bin(num_steps_left))):
		if 1 << i & num_steps_left:
			step_size = 1 << i
			new_ball_counts = [0 for j in range(10)]
			for (ball_val, cnt) in enumerate(ball_counts):
				new_ball_counts = [x + cnt * y for (x, y) in zip(new_ball_counts, dp[step_size][ball_val])]
			return DFS(num_steps_left - step_size, new_ball_counts)
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	(num_balls, multiplier, num_steps) = [int(x) for x in input().split()]
	balls = [int(x) for x in input().strip()]
	dp = dict()
	step_size = 1
	dp[step_size] = dict()
	for ball_val in range(10):
		dp[step_size][ball_val] = [0 for i in range(10)]
		for digit in str(multiplier * ball_val):
			dp[step_size][ball_val][int(digit)] += 1
	step_size *= 2
	while step_size <= num_steps:
		dp[step_size] = dict()
		half_step = step_size // 2
		for ball_val in range(10):
			arr = [0 for i in range(10)]
			for (val, cnt) in enumerate(dp[half_step][ball_val]):
				delta = [cnt * y for y in dp[half_step][val]]
				arr = [(x + y) % mod for (x, y) in zip(arr, delta)]
			dp[step_size][ball_val] = arr
		step_size *= 2
	ball_counts = [0 for i in range(10)]
	for x in balls:
		ball_counts[x] += 1
	ans = sum(DFS(num_steps, ball_counts)) % mod
	print(ans)


import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7

def identity(n):
	matrix = [[0] * n for _ in range(n)]
	for i in range(n):
		matrix[i][i] = 1
	return matrix

def multiply(mat1, mat2):
	(r1, r2) = (len(mat1), len(mat2))
	(c1, c2) = (len(mat1[0]), len(mat2[0]))
	result = [[0] * c2 for _ in range(r1)]
	for i in range(r1):
		for j in range(c2):
			for k in range(r2):
				result[i][j] = (result[i][j] + mat1[i][k] * mat2[k][j]) % MOD
	return result

def power(mat, n):
	res = identity(len(mat))
	while n:
		if n & 1:
			res = multiply(res, mat)
		mat = multiply(mat, mat)
		n = n >> 1
	return res
for _ in range(int(input().strip())):
	(N, K, M) = map(int, input().strip().split())
	S = input().strip()
	mat = [[0] * 10 for _ in range(10)]
	for i in range(10):
		action = str(i * K)
		for s in action:
			mat[int(s)][i] += 1
	mat = power(mat, M)
	vec = [0] * 10
	for s in S:
		vec[int(s)] += 1
	ans = 0
	for i in range(10):
		for j in range(10):
			ans = (ans + mat[i][j] * vec[j]) % MOD
	print(ans)


M = 10 ** 9 + 7

def initNum(inp):
	ret = [[0 for i in range(10)]]
	for i in inp:
		ret[0][int(i)] += 1
	return ret

def cntNum(num):
	cnt = [0 for i in range(10)]
	if num == 0:
		cnt[0] = 1
	while num > 0:
		d = num % 10
		cnt[d] += 1
		num = int(num / 10)
	return cnt

def prepareMultMat(k):
	mat = [[0 for i in range(10)] for j in range(10)]
	for i in range(10):
		num = i * k
		nxtNum = cntNum(num)
		for j in range(10):
			mat[i][j] = (mat[i][j] + nxtNum[j]) % M
	return mat

def matMul(a, b, n, m, c):
	res = [[0 for i in range(c)] for j in range(n)]
	for i in range(n):
		for j in range(c):
			for k in range(m):
				res[i][j] = (res[i][j] + a[i][k] * b[k][j] % M) % M
	return res

def powMat(a, p):
	if p == 1:
		return a
	if p == 2:
		return matMul(a, a, 10, 10, 10)
	at = powMat(a, int(p / 2))
	if p % 2 == 0:
		return matMul(at, at, 10, 10, 10)
	else:
		return matMul(matMul(at, at, 10, 10, 10), a, 10, 10, 10)
t = int(input())
for _ in range(t):
	(n, k, m) = [int(x) for x in input().split()]
	nums = input()
	ini = initNum(nums)
	if m == 0:
		print(sum(ini[0]))
		continue
	mul = powMat(prepareMultMat(k), m)
	ansAr = matMul(ini, mul, 1, 10, 10)
	ans = sum(ansAr[0]) % M
	print(ans)