Given a positive integer X, an operation on X is defined as follows:
Split X into powers of 10 such that the number of integers into which X is split, is minimum.  
Let A define the array containing all integers of the split.
Sort the array A in non-increasing order.
Concatenate the elements of A and assign the value to X.

For example, an operation on X = 22 looks like:
Splitting 22 into minimum number of integers such that each is integer is a power of 10.  
Here, 22 = 1 + 1 + 10 + 10. Thus, A = [1, 1, 10, 10].
Sorting the array A in non-increasing order. Thus, A = [10, 10, 1, 1].
Concatenating the elements of A gives 101011. Thus, the new value of X = 101011.

Kulyash has given you two integers N and K. 

You need to perform the above-mentioned operation K times on the integer N. Find the number of digits in the final integer. Since the answer can be huge, output it modulo 998244353.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The first and only line of each test case contains two space-separated integers N and K — the initial number and the number of operations to be performed.

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

For each test case, output on a new line, the number of digits in the final number after K operations are performed on N, modulo 998244353.

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

$1 ≤ T ≤ 10^{2}$
$1 ≤ N ≤ 10^{10^{4}}$
$0 ≤ K ≤ 10^{9}$

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

Subtask 1 (40 points): $1 ≤ N ≤ 10^{3}$
Subtask 2 (60 points): Original constraints

----- Sample Input 1 ------ 
2
101 3
32 1

----- Sample Output 1 ------ 
6
8

----- explanation 1 ------ 
Test case $1$: Let us perform $3$ operations on $101:$
- Operation $1$ — $101 = 100 + 1$, thus $N = 1001$
- Operation $2$ — $1001 = 1000 + 1$, thus $N = 10001$
- Operation $3$ — $10001 = 10000 + 1$, thus $N = 100001$. The final value of $N$ is $100001$ which has $6$ digits.

Test case $2$: $32 = 10 + 10 + 10 + 1 + 1$, thus $N = 10101011$, which has $8$ digits.

Source: codechef | Difficulty: VERY_HARD
Tags: Matrices

Combinatorics

Mathematics


Solutions:
MOD = 998244353

def modpow(base, exp, mod):
	result = 1
	while exp:
		if exp & 1:
			result = result * base % mod
		base = base * base % mod
		exp >>= 1
	return result

def modinv(base, mod):
	return modpow(base, mod - 2, mod)
MODINV = [modinv(i, MOD) for i in range(9 * 10 ** 4 + 5)]

def main(L, N, K):
	B = [0]
	for i in range(L):
		for _ in range(int(N[L - 1 - i])):
			B.append(B[-1] + (i + 1))
	B = B[::-1]
	K -= 1
	if not K:
		return B[0]
	(S, C) = (0, 1)
	for i in range(len(B)):
		S = (S + B[i] * C) % MOD
		C = C * ((K + i) % MOD) * MODINV[i + 1] % MOD
	return S
T = int(input().strip())
for i in range(T):
	(N, K) = input().strip().split()[:2]
	(L, K) = (len(N), int(K))
	if K == 0:
		print(L)
	else:
		print(main(L, N, K))


mod = 998244353
maxn = 10 ** 6 + 10
invs = [1] * maxn
for i in range(2, maxn):
	invs[i] = (mod - mod // i * invs[mod % i]) % mod
t = int(input())
for _ in range(t):
	(n, k) = input().split()
	k = int(k)
	if k == 0:
		print(len(str(n)))
		continue
	pows = []
	for i in range(len(n)):
		times = ord(n[-1 - i]) - ord('0')
		for j in range(times):
			pows.append(i + 1)
	(ans, coef, n) = (0, 1, len(pows))
	for i in range(n):
		ans += pows[n - 1 - i] * coef
		coef = coef * (k + i) * invs[i + 1] % mod
	print(ans % mod)


mod = 998244353
mxn = 200000
fact = [1] * mxn
inv = [0] * mxn
inv[1] = 1
for i in range(2, mxn):
	fact[i] = fact[i - 1] * i % mod
	inv[i] = pow(fact[i], mod - 2, mod)
for _ in range(int(input())):
	(s, k) = input().split()
	k = int(k)
	if k == 0:
		print(len(s) % mod)
		continue
	i = len(s) - 1
	a = []
	pos = 0
	p = 0
	while i >= 0:
		p += 1
		d = int(s[i])
		while d > 0:
			pos += p
			a.append(pos)
			d -= 1
		i -= 1
	n = len(a)
	if k == 1:
		print(a[n - 1] % mod)
		continue
	a = a[::-1]
	k -= 1
	ans = a[0]
	(nu, de) = (k, 1)
	for i in range(1, n):
		ans = (ans + mod + a[i] * nu * inv[de]) % mod
		nu *= k + i
		nu %= mod
		de += 1
	print(ans % mod)


T = int(input())
mod = 998244353

def inv(x):
	return pow(x, mod - 2, mod)
(fac, ifac) = ([0] * 1000000, [0] * 1000000)
fac[0] = ifac[0] = 1
for i in range(1, 1000000):
	fac[i] = fac[i - 1] * i % mod
ifac[999999] = inv(fac[999999])
for i in reversed(range(1, 999999)):
	ifac[i] = ifac[i + 1] * (i + 1) % mod

def C(n, m):
	return fac[n] * ifac[m] * ifac[n - m] % mod
for i in range(T):
	(N, K) = input().split()
	(l, K) = (len(N), int(K))
	if K == 0:
		print(len(N))
		continue
	A = []
	for c in range(l):
		for _ in range(int(N[c])):
			A.append(l - c)
	A.sort()
	B = 1
	answer = 0
	for i in reversed(range(len(A))):
		n = len(A) - 1 - i + K - 1
		m = len(A) - 1 - i
		answer += A[i] * B * ifac[m] % mod
		B = B * (len(A) - 1 - i + K) % mod
	print(answer % mod)