You are given two integers $l$ and $r$ ($l \le r$). Your task is to calculate the sum of numbers from $l$ to $r$ (including $l$ and $r$) such that each number contains at most $k$ different digits, and print this sum modulo $998244353$.

For example, if $k = 1$ then you have to calculate all numbers from $l$ to $r$ such that each number is formed using only one digit. For $l = 10, r = 50$ the answer is $11 + 22 + 33 + 44 = 110$.


-----Input-----

The only line of the input contains three integers $l$, $r$ and $k$ ($1 \le l \le r < 10^{18}, 1 \le k \le 10$) — the borders of the segment and the maximum number of different digits.


-----Output-----

Print one integer — the sum of numbers from $l$ to $r$ such that each number contains at most $k$ different digits, modulo $998244353$.


-----Examples-----
Input
10 50 2

Output
1230

Input
1 2345 10

Output
2750685

Input
101 154 2

Output
2189



-----Note-----

For the first example the answer is just the sum of numbers from $l$ to $r$ which equals to $\frac{50 \cdot 51}{2} - \frac{9 \cdot 10}{2} = 1230$. This example also explained in the problem statement but for $k = 1$.

For the second example the answer is just the sum of numbers from $l$ to $r$ which equals to $\frac{2345 \cdot 2346}{2} = 2750685$.

For the third example the answer is $101 + 110 + 111 + 112 + 113 + 114 + 115 + 116 + 117 + 118 + 119 + 121 + 122 + 131 + 133 + 141 + 144 + 151 = 2189$.

Difficulty: HARD
Tags: Dynamic programming

Bit manipulation

Combinatorics

Mathematics
Skill types: Dynamic programming

Bit manipulation

Starter code:

Solutions:
MOD = 998244353

def pop_count(x):
	ans = 0
	while x > 0:
		ans = ans + x % 2
		x = x // 2
	return ans

def check(x, k):
	mask = 0
	nx = int(x)
	while nx > 0:
		mask = mask | 1 << nx % 10
		nx = nx // 10
	if pop_count(mask) <= k:
		return x
	return 0
pop = []
p10 = []
f = [[0 for j in range(1 << 10)] for i in range(20)]
w = [[0 for j in range(1 << 10)] for i in range(20)]

def prepare():
	p10.append(1)
	for i in range(20):
		p10.append(p10[i] * 10 % MOD)
	for i in range(1 << 10):
		pop.append(pop_count(i))
	w[0][0] = 1
	for i in range(1, 20):
		for j in range(1 << 10):
			for use in range(10):
				w[i][j | 1 << use] = (w[i][j | 1 << use] + w[i - 1][j]) % MOD
				f[i][j | 1 << use] = (f[i][j | 1 << use] + w[i - 1][j] * use * p10[i - 1] + f[i - 1][j]) % MOD

def solve(x, k):
	sx = [int(d) for d in str(x)]
	n = len(sx)
	ans = 0
	for i in range(1, n):
		for use in range(1, 10):
			for mask in range(1 << 10):
				if pop[1 << use | mask] <= k:
					ans = (ans + f[i - 1][mask] + use * w[i - 1][mask] % MOD * p10[i - 1]) % MOD
	cmask = 0
	csum = 0
	for i in range(n):
		cdig = sx[i]
		for use in range(cdig):
			if i == 0 and use == 0:
				continue
			nmask = cmask | 1 << use
			for mask in range(1 << 10):
				if pop[nmask | mask] <= k:
					ans = (ans + f[n - i - 1][mask] + (csum * 10 + use) * w[n - i - 1][mask] % MOD * p10[n - i - 1]) % MOD
		cmask |= 1 << cdig
		csum = (10 * csum + cdig) % MOD
	return ans
prepare()
(l, r, k) = list(map(int, input().split()))
ans = (check(r, k) + solve(r, k) - solve(l, k) + MOD) % MOD
print(ans)


import sys
mod = 998244353
MAX_LENGTH = 20
bound = [0] * MAX_LENGTH

def mul(a, b):
	return a * b % mod

def add(a, b):
	a += b
	if a < 0:
		a += mod
	if a >= mod:
		a -= mod
	return a

def digitize(num):
	for i in range(MAX_LENGTH):
		bound[i] = num % 10
		num //= 10

def rec(smaller, start, pos, mask):
	global k
	if bit_count[mask] > k:
		return [0, 0]
	if pos == -1:
		return [0, 1]
	if dp[smaller][start][pos][mask][0] != -1:
		return dp[smaller][start][pos][mask]
	res_sum = res_ways = 0
	for digit in range(0, 10):
		if smaller == 0 and digit > bound[pos]:
			continue
		new_smaller = smaller | (digit < bound[pos])
		new_start = start | (digit > 0) | (pos == 0)
		new_mask = mask | 1 << digit if new_start == 1 else 0
		(cur_sum, cur_ways) = rec(new_smaller, new_start, pos - 1, new_mask)
		res_sum = add(res_sum, add(mul(mul(digit, ten_pow[pos]), cur_ways), cur_sum))
		res_ways = add(res_ways, cur_ways)
	(dp[smaller][start][pos][mask][0], dp[smaller][start][pos][mask][1]) = (res_sum, res_ways)
	return dp[smaller][start][pos][mask]

def solve(upper_bound):
	global dp
	dp = [[[[[-1, -1] for _ in range(1 << 10)] for _ in range(MAX_LENGTH)] for _ in range(2)] for _ in range(2)]
	digitize(upper_bound)
	ans = rec(0, 0, MAX_LENGTH - 1, 0)
	return ans[0]
inp = [int(x) for x in sys.stdin.read().split()]
(l, r, k) = (inp[0], inp[1], inp[2])
bit_count = [0] * (1 << 10)
for i in range(1, 1 << 10):
	bit_count[i] = bit_count[i & i - 1] + 1
ten_pow = [1]
for i in range(MAX_LENGTH):
	ten_pow.append(mul(ten_pow[-1], 10))
print(add(solve(r), -solve(l - 1)))


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	(l, r, k) = map(int, input().split())
	(valid_bits, is_valid_bits) = ([], [0] * 1024)
	for bit in range(1024):
		if bin(bit).count('1') <= k:
			valid_bits.append(bit)
			is_valid_bits[bit] = 1
	mod = 998244353

	def solve(ub):
		dp = array('i', [0]) * 1024
		dp_cnt = array('i', [0]) * 1024
		next_dp = array('i', [0]) * 1024
		next_dp_cnt = array('i', [0]) * 1024
		(boundary_dp, b_bit) = (0, 0)
		for (e, digit) in zip(range(len(str(ub)) - 1, -1, -1), map(int, str(ub))):
			base = pow(10, e, mod)
			for bit in valid_bits:
				for d in range(10):
					nextbit = bit | 1 << d
					if is_valid_bits[nextbit]:
						next_dp[nextbit] = (next_dp[nextbit] + dp[bit] + base * d * dp_cnt[bit]) % mod
						next_dp_cnt[nextbit] += dp_cnt[bit]
						if next_dp_cnt[nextbit] >= mod:
							next_dp_cnt[nextbit] -= mod
			for d in range(digit):
				nextbit = b_bit | 1 << d
				if is_valid_bits[nextbit]:
					next_dp[nextbit] = (next_dp[nextbit] + boundary_dp + base * d) % mod
					next_dp_cnt[nextbit] += 1
			b_bit |= 1 << digit
			boundary_dp = (boundary_dp + base * digit) % mod
			for i in valid_bits:
				dp[i] = next_dp[i]
				dp_cnt[i] = next_dp_cnt[i]
				next_dp[i] = next_dp_cnt[i] = 0
			(dp[0], dp_cnt[0]) = (0, 1)
			dp[1] = dp_cnt[1] = 0
		return (sum(dp) + (boundary_dp if is_valid_bits[b_bit] else 0)) % mod
	print((solve(r) - solve(l - 1)) % mod)
main()


(l, r, k) = list(map(int, input().split()))
d = {i: 2 ** i for i in range(10)}
cache = {}

def can(i, m):
	return d[i] & m

def calc(m):
	b = 1
	c = 0
	for i in range(10):
		if b & m:
			c += 1
		b *= 2
	return c

def sm(ln, k, m, s='', first=False):
	if ln < 1:
		return (0, 1)
	if (ln, k, m, s, first) in cache:
		return cache[ln, k, m, s, first]
	ans = 0
	count = 0
	base = 10 ** (ln - 1)
	use_new = calc(m) < k
	if s:
		finish = int(s[0]) + 1
	else:
		finish = 10
	for i in range(finish):
		if use_new or can(i, m):
			ss = s[1:]
			if i != finish - 1:
				ss = ''
			nm = m | d[i]
			nfirst = False
			if i == 0 and first:
				nm = m
				nfirst = True
			(nexta, nextc) = sm(ln - 1, k, nm, ss, nfirst)
			ans += base * i * nextc + nexta
			count += nextc
	cache[ln, k, m, s, first] = (ans, count)
	return (ans, count)

def call(a, k):
	s = str(a)
	return sm(len(s), k, 0, s, True)[0]
print((call(r, k) - call(l - 1, k)) % 998244353)