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

public class G_digitalDP {
    static int mod = 998244353;
    static int k;
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
 
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
 
        public int nextInt() {
            return Integer.parseInt(next());
        }
 
        public long nextLong() {
            return Long.parseLong(next());
        }

 }
    static int addNumbers(int mask, int idx, int less, int start){
        if(start == 0)
            mask = 0;
        if(idx == 19)
            return 0;
        if(dp2[less][start][idx][mask] != -1)
            return dp2[less][start][idx][mask];

        int ans = 0;
        for (int i = 0; i < 10 && (less == 1 || number[idx] >= i); i++) {
            int newMask = mask | (1<<i);
            int newLess = less | (number[idx] > i?1:0);
            int newStart = start | (i > 0?1:0);
            int addedWt = mult(mult(i, wwwwwwwwwwwwwwwwwwwwwww[idx]), count(newMask, idx+1, newLess, newStart));
            ans = add(ans, addNumbers(newMask, idx+1, newLess, newStart));
            ans = add(ans, addedWt);
        }


        return dp2[less][start][idx][mask] = ans;
    }


    static int sub(long a, long b){
        return (int)((((a-b)%mod)+mod)%mod);
    }
    public static void main(String []args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        int u=121;
        slove(in,out);
        out.close();
    }
    static void slove(InputReader in, PrintWriter out){   //Slove 里的内容是真正的解题代码
    
    	long l = in.nextLong();
        long r = in.nextLong();
        k = in.nextInt();

        dp1 = new int[2][2][20][1500];
        dp2 = new int[2][2][20][1500];

        wwwwwwwwwwwwwwwwwwwwwww = new long[19];
        wwwwwwwwwwwwwwwwwwwwwww[wwwwwwwwwwwwwwwwwwwwwww.length-1] = 1;
        for (int i = wwwwwwwwwwwwwwwwwwwwwww.length-2; i >= 0; i--) {
            wwwwwwwwwwwwwwwwwwwwwww[i] = wwwwwwwwwwwwwwwwwwwwwww[i+1]*10;
            wwwwwwwwwwwwwwwwwwwwwww[i] %= mod;
        }

        long ans = solveCnt(r);
        if(l > 0)
            ans = sub(ans, solveCnt(l-1));

        out.println(ans);
    }

    static int solveCnt(long n){
        number = new int[19];
        int idx = 18;
        while(n > 0){
            number[idx--] = (int)(n%10);
            n/=10;
        }

        for (int i = 0; i < dp1.length; i++) {
            for (int j = 0; j < dp1[i].length; j++) {
                for (int l = 0; l < dp1[i][j].length; l++) {
                    Arrays.fill(dp1[i][j][l], -1);
                    Arrays.fill(dp2[i][j][l], -1);
                }
            }
        }

        count(0, 0, 0, 0);
        return addNumbers(0, 0, 0, 0);

    }

    static int[] number;
    static long wwwwwwwwwwwwwwwwwwwwwww[];
    static int[][][][] dp1;
    static int[][][][] dp2;

    static int count(int mask, int idx, int less, int start){
        if(start == 0)
            mask = 0;
        if(idx == 19){
            if(Integer.bitCount(mask) <= k)
                return 1;
            return 0;
        }

        if(dp1[less][start][idx][mask] != -1)
            return dp1[less][start][idx][mask];

        int ans = 0;
        for (int i = 0; i < 10 && (less == 1 || i<=number[idx]) ; i++) {
            int newMask = mask | (1<<i);
            int newstart = start;
            if(i > 0)
                newstart = 1;
            int newLess = less | (i < number[idx]?1:0);
            ans = add(ans, count(newMask, idx+1, newLess, newstart));

        }

        return dp1[less][start][idx][mask] = ans;
    }

    static int add(long a, long b){
        return (int)((a+b)%mod);
    }

    static int mult(long a, long b){
        return (int)(1l*a*b%mod);
    }




    

}