You are given two integers l and r (l ≤ 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 ≤ l ≤ r < 10^{18}, 1 ≤ k ≤ 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 (50 ⋅ 51)/(2) - (9 ⋅ 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 (2345 ⋅ 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.



l, r, k =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)
