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.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;
import java.io.*;



public class Main {
    private static pair [] [] [] [] dp ;
    private static int [] digits;
    private static int [] popcnt;
    private static int K;
    private static long mod = 998244353L;
    private static long [] p10;
    private static pair solve(int i,int msk,int eq,int is_zero) {
        if (popcnt[msk] > K) return new pair(0,0);
        if (i == digits.length) return new pair(1,0);
        if (dp[i][msk][eq][is_zero] != null) return dp[i][msk][eq][is_zero];
        pair ret = new pair(0,0);
        for (int d = 0;d < 10;d++) {
            pair tmp = new pair(0,0);
            if (eq == 1) {
                if (d > digits[i]) break;
                int zero = is_zero ;
                if (d != 0) zero = 0;
                int n_msk = msk | (1 << d);
                if (zero==1) n_msk = 0;
                tmp = solve(i+1,n_msk,(d == digits[i]) ? 1 : 0,zero);
            }
            else {
                int zero = is_zero ;
                if (d != 0) zero = 0;
                int n_msk = msk | (1 << d);
                if (zero==1) n_msk = 0;
                tmp = solve(i+1,n_msk,0,zero);
            }
            ret.sum += tmp.sum + d*tmp.cnt*p10[digits.length-1-i];
            ret.sum %= mod;
            ret.cnt += tmp.cnt;
            ret.cnt %= mod;
        }
        dp[i][msk][eq][is_zero] = ret;
        return ret;
    }
    private static pair solve(long x) {
        popcnt = new int[1 << 10];
        for (int msk = 0;msk < popcnt.length;msk++)
            popcnt[msk] = popcnt[msk >> 1] + (msk&1);
        p10 = new long[20];
        p10[0] = 1;
        for (int i = 1;i < p10.length;i++)
            p10[i] = (p10[i-1]*10)%mod;
        String sx = Long.toString(x);
        digits = new int[sx.length()];
        for (int i = 0;i < digits.length;i++)
            digits[i] = sx.charAt(i) - '0';
        dp = new pair[digits.length][1 << 10][2][2];
        return solve(0,0,1,1);
    }

    public static void main(String[] args) throws Exception {
        IO io ;
        try {
            io = new IO("in.in", null);
        } catch (IOException e) {
            io = new IO(null, null);
        }
        long l = io.getNextLong(),r = io.getNextLong();
        K = io.getNextInt();
        pair a = solve(l-1),b = solve(r);
        long ans = b.sum - a.sum;
//        System.err.println(a + " " + b);
        if (ans < 0) ans += mod;
        io.println(ans);
        io.close();
    }
    private static final int onebillion7 = 1000000007;
}


class pair{
    long sum,cnt;
    public pair(long a,long b) {
        cnt = a;
        sum = b;
    }
    @Override
    public String toString(){
        return "(" + cnt + ", " + sum + ")";
    }
}

class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }

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

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}