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.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.io.InputStream;

/**
 * @author khokharnikunj8
 */

public class Main {
    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                new Main().solve();
            }
        }, "1", 1 << 26).start();
    }

    void solve() {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ESegmentSum solver = new ESegmentSum();
        solver.solve(1, in, out);
        out.close();
    }

    static class ESegmentSum {
        long[][] dp;
        long[][] ct;
        long[] pow;
        int k;
        long mod = 998244353;
        ArrayList<Integer> arrayList;

        private pair findIt(int index, int mask, int sum, boolean tight) {
            if (index == -1) {
                if (mask == 0) return new pair(0, 0);
                if (Integer.bitCount(mask) <= k) return new pair(sum, 1);
                return new pair(0, 0);
            }
            if (dp[index][mask] != -1 && !tight)
                return new pair((((((ct[index][mask] * pow[index + 1]) % mod) * sum) % mod) + dp[index][mask]) % mod, ct[index][mask]);
            int limit = tight ? arrayList.get(index) : 9;
            dp[index][mask] = 0;
            ct[index][mask] = 0;
            for (int i = 0; i <= limit; i++) {
                boolean newBOund = tight & (i == arrayList.get(index));
                pair pp = findIt(index - 1, ((mask == 0 && i == 0) ? 0 : mask | (1 << i)), i, newBOund);
                dp[index][mask] = (dp[index][mask] + pp.x) % mod;
                ct[index][mask] = (ct[index][mask] + pp.y) % mod;
            }
            return new pair((((((ct[index][mask] * pow[index + 1]) % mod) * sum) % mod) + dp[index][mask]) % mod, ct[index][mask]);
        }

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            dp = new long[21][1024];
            ct = new long[21][1024];
            pow = new long[21];
            pow[0] = 1;
            for (int i = 1; i < 21; i++) pow[i] = (pow[i - 1] * 10) % mod;
            long a, b;
            for (int i = 0; i < 20; i++)
                for (int j = 0; j < 1024; j++) {
                    dp[i][j] = -1;
                    ct[i][j] = -1;
                }
            a = in.scanLong();
            b = in.scanLong();
            k = in.scanInt();

            filArray(b);
            long ans1 = findIt(arrayList.size() - 1, 0, 0, true).x;

            for (int i = 0; i < 20; i++)
                for (int j = 0; j < 1024; j++) {
                    dp[i][j] = -1;
                    ct[i][j] = -1;
                }

            filArray(a - 1);
            long ans2 = findIt(arrayList.size() - 1, 0, 0, true).x;
            long ans = (ans1 - ans2) % mod;
            while (ans < 0) ans += mod;
            out.println(ans % mod);
        }

        private void filArray(long a) {
            arrayList = new ArrayList<>();
            while (a > 0) {
                arrayList.add((int) (a % 10));
                a /= 10;
            }
        }

        class pair {
            long x;
            long y;

            public pair(long x, long y) {
                this.x = x;
                this.y = y;
            }

        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public int scanInt() {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

        public long scanLong() {
            long integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

    }
}

