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.util.*;
import java.io.*;

public class Div712 {
    ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////                                                                                                               /////////
////////                                                                                                               /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM         OOOOOO             SSSSSSS      EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMMMM      MMMMMM      OOO      OOO        SSSS   SSS     EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEE           MMMM MMM  MMM MMMM    OOO          OOO    SSSS       SSS   EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM  MMMMMM  MMMM   OOO            OOO   SSSS             EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM  OOO              OOO   SSSSSSS         EEEEE          /////////
////////   HHHHHHHHHHHHHHHH  EEEEEEEEEEE     MMMM          MMMM  OOO              OOO      SSSSSS       EEEEEEEEEEE    /////////
////////   HHHHHHHHHHHHHHHH  EEEEEEEEEEE     MMMM          MMMM  OOO              OOO         SSSSSSS   EEEEEEEEEEE    /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM   OOO            OOO              SSSS  EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM    OOO          OOO     SSS       SSSS  EEEEE          /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM      OOO      OOO        SSS    SSSS    EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM         OOOOOO             SSSSSSS      EEEEEEEEEEEEE  /////////
////////                                                                                                               /////////
////////                                                                                                               /////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    static int mod = 998244353;
    static int[][][] memo, memo2;
    static int k;
    static int[] s;
    static long pow10[];

    static int dp(int limit, int idx, int taken) {
        if (Integer.bitCount(taken) > k)
            return 0;
        if (idx == 19)
            return 1;
        if (memo[limit][idx][taken] != -1)
            return memo[limit][idx][taken];
        int ans = 0;
        for (int i = 0; i < 10; i++) {
            if (!can(limit, idx, i))
                continue;
            if (i == 0 && taken == 0) {
                ans += dp(getl(limit, idx, i), idx + 1, taken);
            } else ans += dp(getl(limit, idx, i), idx + 1, taken | 1 << i);
            ans %= mod;
        }
        return memo[limit][idx][taken] = ans;
    }

    static int dp2(int limit, int idx, int taken) {
        if (Integer.bitCount(taken) > k)
            return 0;
        if (idx == 19)
            return 0;
        if (memo2[limit][idx][taken] != -1)
            return memo2[limit][idx][taken];
        long ans = 0;
        for (int i = 0; i < 10; i++) {
            if (!can(limit, idx, i))
                continue;
            if (i == 0 && taken == 0) {
                ans += dp2(getl(limit, idx, i), idx + 1, taken);
            } else {
                long v = dp2(getl(limit, idx, i), idx + 1, taken | 1 << i);
                long count = dp(getl(limit, idx, i), idx + 1, taken | 1 << i);
                v += (count * i * pow10[18 - idx]);
                v %= mod;
                ans += v;
            }
            ans %= mod;
        }
        return memo2[limit][idx][taken] = (int) ans;
    }

    static int getl(int limit, int idx, int d) {
        return limit | (s[idx] > d ? 1 : 0);
    }

    static boolean can(int limit, int idx, int d) {
        return limit == 1 | (s[idx] >= d);
    }

    static int dpvalue(long v) {
        s = new int[19];

        int idx = 18;
        while (idx >= 0) {
            s[idx] = (int) (v % 10);
            v /= 10;
            idx--;
        }
        memo = new int[2][19][1 << 10];
        memo2 = new int[2][19][1 << 10];

        for (int[][] x : memo) for (int[] y : x) Arrays.fill(y, -1);
        for (int[][] x : memo2) for (int[] y : x) Arrays.fill(y, -1);
//        System.err.println(Arrays.toString(s));
//        System.err.println(v + " " + dp2(0, 17, 0));
        return dp2(0, 0, 0);
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        pow10 = new long[20];
        pow10[0] = 1;
        for (int i = 1; i < 20; i++) {
            pow10[i] = (10 * pow10[i - 1]) % mod;
        }

        long l = sc.nextLong();
        long r = sc.nextLong();
        k = sc.nextInt();
        long ans = dpvalue(r) - dpvalue(l - 1) + mod;

        pw.println(ans % mod);

        pw.flush();
    }


    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int[] nextIntArr(int n) throws IOException {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException {
            return br.ready();
        }
    }

}
