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: interview

Starter code:

Solutions:



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

#    print(ln, k, m, s, first, ans, count)
    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))
print((call(r, k) - call(l-1, k)) % 998244353)



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)