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 Main {
    static int INF = 1001001009;
    static Scanner sc = new Scanner(System.in);
    static PrintWriter out = new PrintWriter(System.out);
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    long mod = 998244353;

    int[] ones = new int[1<<10];
    long[] power_10 = new long[20];
    boolean[][] vis;
    long[][][] dp;
    int k;
    public static void main(String[] args) throws Exception {
        // Your code here!
        Main main = new Main();

        main.solve();
//        long ans = main.solve();
//        out.println(ans);
        out.flush();
    }
    void solve() throws Exception{
        long l = sc.nextLong(), r = sc.nextLong();
        k = sc.nextInt();
        for(int i=1; i<(1<<10); i++){
            ones[i] = count_one(i);
        }
        power_10[0] = 1;
        for(int i=1; i<20; i++) power_10[i] = power_10[i-1]*10%mod;
        long res1 = solve(l-1);
        long res2 = solve(r);
        long ans = (res2+mod-res1)%mod;
        out.println(ans);
    }
    int count_one(int n){
        int ans = 0;
        while(n>0){
            ans += n&1;
            n = n/2;
        }
        return ans;
    }
    long solve(long x){
        if(x==0) return 0;
        char[] arr = Long.toString(x).toCharArray();
        int len = arr.length;
        int[] a = new int[len+1];
        for(int i=1; i<=len; i++) a[i] = arr[len-i]-'0';
        vis = new boolean[len+1][1<<10];
        dp = new long[len+1][1<<10][2];
        long ans = 0;
        for(int i=1; i<=len; i++){ // the length of target numbers
            int upper = 9;
            if(i==len) upper = a[len];
            for(int j=1; j<=upper; j++){
                long[] tmp = dfs(i, 1<<j, (i==len)&(j==a[len]), a);
                ans += tmp[1]*j%mod*power_10[i-1]%mod;
                ans %= mod;
                ans = (ans+tmp[0])%mod;
            }
        }
        return ans%mod;
    }
    long[] dfs(int pos, int state, boolean is_limit, int[] a){
        if((!is_limit)&&vis[pos][state]) return dp[pos][state];
        if(pos==1) return new long[]{0, 1};
        int upper = 9;
        long[] ans = new long[2];
        if(is_limit) upper = a[pos-1]; // consider lower one bit. Directly determined by the main function.
        for(int i=0; i<=upper; i++){
            int mask = state | (1<<i);
            if(ones[mask]<=k){
                long[] tmp = dfs(pos-1, mask, is_limit && i== upper, a);
                ans[1] = (ans[1]+tmp[1])%mod;
                ans[0] = (ans[0]+tmp[0])%mod;
                ans[0] = (i*power_10[pos-2]%mod*tmp[1]%mod + ans[0])%mod; // this "-2" also determined by the meaning of pos
            }
        }
        vis[pos][state] = true;
        return dp[pos][state] = ans;
    }
    int paIn(String s){return Integer.parseInt(s);}
}