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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Vadim
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        long[][] dsum = new long[19][1024];
        long[][] dcnt = new long[19][1024];
        long[] ssum = new long[19];
        long[] scnt = new long[19];
        long mod = 998244353;
        int[] nbits = new int[1024];
        long[] p10 = new long[19];
        int k;

        long getSum(int len) {
            long res = 0;
            for (int i = 1; i <= len; i++) {
                res += ssum[i];
                res %= mod;
            }
            return res % mod;
        }

        long getSum(int prefixMask, int len) {
            if (len == 0)
                return 0;
            long res = 0;
            for (int mask = 1; mask < 1024; mask++) {
                if (nbits[mask | prefixMask] <= k) {
                    res += dsum[len][mask];
                    res %= mod;
                }
            }
            return res % mod;
        }

        long getCnt(int prefixMask, int len) {
            if (nbits[prefixMask] > k)
                return 0;
            if (len == 0)
                return 1;
            long res = 0;
            for (int mask = 1; mask < 1024; mask++) {
                if (nbits[mask | prefixMask] <= k) {
                    res += dcnt[len][mask];
                    res %= mod;
                }
            }
            return res % mod;
        }

        long calc(long num) {
            String s = Long.toString(num);
            int len = s.length() - 1;
            long res = 0;
            int prefixMask = 0;
            long prefix = 0;
            for (int i = 0; i < s.length(); i++) {
                int d = s.charAt(i) - '0';
                prefix *= 10;
                for (int x = 0; x < d; x++) {
                    int mask = prefixMask | 1 << x;
                    long curPrefix = prefix + x;
                    if (i == 0 && x == 0)
                        res += getSum(len);
                    else
                        res += curPrefix * p10[len] % mod * getCnt(mask, len) % mod + getSum(mask, len);
                    res %= mod;
                }
                prefix += d;
                prefixMask |= 1 << d;
                len--;
            }
            return res;
        }

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            long l = in.nl();
            long r = in.nl();
            k = in.ni();

            p10[0] = 1;
            for (int i = 1; i <= 18; i++) {
                p10[i] = p10[i - 1] * 10 % mod;
            }

            for (int i = 0; i < 1024; i++) {
                nbits[i] = Integer.bitCount(i);
            }

            for (int i = 0; i < 10; i++) {
                dsum[1][1 << i] = i;
                dcnt[1][1 << i] = 1;
            }
            ;
            scnt[1] = 9;
            ssum[1] = 45;
            for (int len = 2; len < 19; len++) {
                for (int d = 0; d <= 9; d++) {
                    int bit = 1 << d;
                    for (int mask = 1; mask < 1024; mask++) {
                        int newMask = mask | bit;
                        if (nbits[newMask] <= k) {
                            dcnt[len][newMask] += dcnt[len - 1][mask];
                            long subsum = d * p10[len - 1] * dcnt[len - 1][mask] + dsum[len - 1][mask];
                            dsum[len][newMask] += subsum;
                            dcnt[len][newMask] %= mod;
                            dsum[len][newMask] %= mod;
                            if (d != 0) {
                                scnt[len] += dcnt[len - 1][mask];
                                ssum[len] += subsum;
                                scnt[len] %= mod;
                                ssum[len] %= mod;
                            }
                        }
                    }
                }


            }

            out.println((calc(r + 1) - calc(l) + mod) % mod);
        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String ns() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int ni() {
            return Integer.parseInt(ns());
        }

        public long nl() {
            return Long.parseLong(ns());
        }

    }
}

