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.
//package com.company;

import java.io.*;
import java.util.*;

public class Main {
    static long TIME_START, TIME_END;

    public static class Task {
        long[][] cnk;
        public void precompute() {
            cnk = new long[20][20];
            for (int i = 0; i < 20; i++) {
                cnk[i][i] = cnk[i][0] = 1;
            }
            for (int i = 2; i < 20; i++) {
                for (int j = 1; j < i; j++) {
                    cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % mod;
                }
            }
        }

        public void solve(Scanner sc, PrintWriter pw) throws IOException {
            precompute();
            dpSum = new long[1 << 10][20][2];
            for (long[][] x : dpSum) {
                for (long[] y : x)
                    Arrays.fill(y, -1);
            }
            dpCount = new long[11][20];
            for (int i = 0; i < 11; i++) {
                dpCount[i][0] = 1;
                for (int j = 1; j < 20; j++) {
                    dpCount[i][j] = dpCount[i][j - 1] * i % mod;
                }
            }
            long l = sc.nextLong();
            long r = sc.nextLong();
            int k = sc.nextInt();
            long rr = ddp(r, k);
            long ll = ddp(l - 1, k);
            pw.println((rr + mod - ll) % mod);
        }
        public long ddp(long x, int k) {
            num = new int[20];
            int idx = 0;
            while (x != 0) {
                num[++idx] = (int) (x % 10);
                x /= 10;
            }
            long cor = 0;
            for (int i = 0; i < 1 << 10; i++) {
                int v = Integer.bitCount(i);
                if (v <= k) {
                    long amt = 0;
                    for (int j = 0; v + j <= k; j++) {
                        amt = (amt + (cnk[10 - v][j] * (j % 2 == 0 ? 1 : mod - 1)) % mod) % mod;
                    }
                    cor = (cor + amt * digitDP(idx, i, 0,true, false) % mod) % mod;
                }
            }
            return cor;
        }
        int mod = 998244353;
        long[][] dpCount; // choose, size
        long[][][] dpSum; // use digit, remain pos,
        int[] num;
        public long digitDP(int pos, int mask, long prefix, boolean bad, boolean st) {
            if (pos == 0) return prefix;
            if (!bad && dpSum[mask][pos][st ? 1 : 0] != -1) {
                long x = getCount(pos, mask, st);
                long y = dpSum[mask][pos][st ? 1 : 0];
                for (int i = 0; i < pos; i++) {
                    prefix = prefix * 10 % mod;
                }
                return (x * prefix % mod + y) % mod;
            }
            int max = bad ? num[pos] : 9;
            long sum = 0;
            for (int i = 0; i <= max; i++) {
                if (((1 << i) | mask) == mask)
                    sum = (sum + digitDP(pos - 1,  mask, (prefix * 10 % mod + i) % mod,
                            bad && (i == max), st || (i != 0))) % mod;
                else if (i == 0 && !st) {
                    sum = (sum + digitDP(pos - 1,  mask, (prefix * 10 % mod + i) % mod,
                            bad && (i == max), false)) % mod;
                }
            }
            if (bad) {
                return sum;
            }
            for (int i = 0; i < pos; i++) {
                prefix = prefix * 10 % mod;
            }
            long y = (sum - getCount(pos, mask, st) * prefix % mod + mod) % mod;
            dpSum[mask][pos][st ? 1 : 0] = y;
            return sum;
        }

        public long getCount(int pos, int mask, boolean start) {
            int v = Integer.bitCount(mask);
            if (start || (mask | 1) == mask) return dpCount[v][pos];
            long s = 0;
            for (int i = 1; i <= pos; i++) {
                s += dpCount[v][pos];
            }
            return s;
        }

    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
//        Scanner sc = new Scanner(new FileInputStream("Test.in"));
        PrintWriter pw = new PrintWriter(System.out);
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.in"));
//        PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out"));
        Runtime runtime = Runtime.getRuntime();
        long usedMemoryBefore = runtime.totalMemory() - runtime.freeMemory();
        TIME_START = System.currentTimeMillis();
        Task t = new Task();
        t.solve(sc, pw);
        TIME_END = System.currentTimeMillis();
        long usedMemoryAfter = runtime.totalMemory() - runtime.freeMemory();
        pw.close();
//        System.out.println("Memory increased:" + (usedMemoryAfter - usedMemoryBefore) / 1000000);
//        System.out.println("Time used: " + (TIME_END - TIME_START) + ".");
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

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

        public Scanner(FileReader s) throws FileNotFoundException {
            br = new BufferedReader(s);
        }

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

        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 {
            return Double.parseDouble(next());
        }

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