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

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

    static class ESegmentSum {
        char[] l;
        char[] r;
        int k;
        char[] arr;
        long[] pow;
        int mod = 998244353;
        long[][][][] memo;
        long[][][][] memo2;

        public void readInput(Scanner sc) {
            l = ((sc.nextLong() - 1) + "").toCharArray();
            r = (sc.nextLong() + "").toCharArray();
            k = sc.nextInt();
        }

        public void solve(int testNumber, Scanner sc, PrintWriter pw) {
            int q = 1;
            while (q-- > 0) {
                readInput(sc);
                pow = new long[20];
                pow[0] = 1;
                for (int i = 1; i < pow.length; i++) {
                    pow[i] = (10 * pow[i - 1]);
                    pow[i] %= mod;
                }
                long ans = dp(r);
                pw.println((ans - dp(l) + mod) % mod);
            }
        }

        private long dp(char[] a) {
            arr = a;
            memo = new long[2][2][arr.length][1 << 10];
            for (long[][][] x : memo)
                for (long[][] y : x)
                    for (long[] z : y)
                        Arrays.fill(z, -1);
            memo2 = new long[2][2][arr.length][1 << 10];
            for (long[][][] x : memo2)
                for (long[][] y : x)
                    for (long[] z : y)
                        Arrays.fill(z, -1);
            return dp(0, 0, 0, 0);
        }

        private long dp(int idx, int msk, int bool, int bool2) {
            if (idx == arr.length)
                return 0;
            if (memo[bool][bool2][idx][msk] != -1)
                return memo[bool][bool2][idx][msk];
            int e = bool == 1 ? 9 : arr[idx] - '0';
            long ans = 0;
            for (int i = 0; i <= e; i++) {
                int nextBool = i < arr[idx] - '0' ? 1 : bool;
                int nextBool2 = i != 0 ? 1 : bool2;
                int nextMsk = nextBool2 == 1 ? msk | 1 << i : msk;
                long temp = count(idx + 1, nextMsk, nextBool, nextBool2);
                if (temp == 0)
                    continue;
                temp *= pow[arr.length - 1 - idx];
                temp %= mod;
                temp *= i;
                ans += temp;
                ans += dp(idx + 1, nextMsk, nextBool, nextBool2);
                ans %= mod;
            }
            return memo[bool][bool2][idx][msk] = ans;
        }

        private long count(int idx, int msk, int bool, int bool2) {
            if (idx == arr.length)
                return bool2 == 1 && Integer.bitCount(msk) <= k ? 1 : 0;
            if (memo2[bool][bool2][idx][msk] != -1)
                return memo2[bool][bool2][idx][msk];
            int e = bool == 1 ? 9 : arr[idx] - '0';
            long ans = 0;
            for (int i = 0; i <= e; i++) {
                int nextBool = i < arr[idx] - '0' ? 1 : bool;
                int nextBool2 = i != 0 ? 1 : bool2;
                int nextMsk = nextBool2 == 1 ? msk | 1 << i : msk;
                ans += count(idx + 1, nextMsk, nextBool, nextBool2);
                ans %= mod;
            }
            return memo2[bool][bool2][idx][msk] = ans;
        }

    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

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

        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }

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

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

    }
}

