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.*;
import java.util.*;
public class Task{
    public static void main(String[] args) throws IOException{
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
//        PrintWriter out = new PrintWriter(new FileWriter("G:\\o.txt"));
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.flush();out.close();
    }
        static class TaskE {
          //0->ways 1->sum
          long l,r;int k;
          final int mod=998244353;
          long dp[][][]=new long[20][1024][2];
          long p10[]=new long[20];
          void pre(){
             p10[0]=1;
             for(int i=1;i<20;i++)p10[i]=10*p10[i-1];
          }
          long sub(long a,long b){
             a-=b;
             if(a<0)a+=mod;
             return a;
          }
          long add(long a,long b){
             a+=b;
             if(a>=mod)a-=mod;
             return a;
          }
          long mul(long a,long b){
             a%=mod;b%=mod;
             a*=b;
             if(a>=mod)a%=mod;
             return a;             
          }
          long[] rec1(int id,int mask,int maxlength){
             if(id==maxlength-1)return new long[]{0,0};
             if(dp[id][mask][0]!=-1)return dp[id][mask];
             dp[id][mask][0]=dp[id][mask][1]=0;
             for(int i=0;i<=9;i++){
                int newmask=mask|(1<<i);
                if(Integer.bitCount(newmask)>k)continue;
                int add=(i==0)?0:1;
                long A[]=rec1(id+1,newmask,maxlength);
                long ways=add(add,A[0]);
                dp[id][mask][0]=add(dp[id][mask][0],ways);
                dp[id][mask][1]=add(dp[id][mask][1],add(A[1],mul(ways,mul(p10[id],i))));
             }return dp[id][mask];
          }
          long[] rec2(int id,int mask,int maxlength,boolean flag,String no){
            if(id==maxlength)return new long[]{1,0};
            if(flag&&dp[id][mask][0]!=-1)return dp[id][mask];
            dp[id][mask][0]=dp[id][mask][1]=0;
            int ed=9,st=0;
            if(!flag){
              ed=get(no,id);
            }
            if(id==0)st=1;
            for(int i=st;i<=ed;i++){
                int newmask=mask|(1<<i);
                boolean newflag=flag||i<ed?true:false;
                if(Integer.bitCount(newmask)>k)continue;
                long A[]=rec2(id+1,newmask,maxlength,newflag,no);
                dp[id][mask][0]=add(dp[id][mask][0],A[0]);
                dp[id][mask][1]=add(dp[id][mask][1],add(A[1],mul(A[0],mul(p10[maxlength-id-1],i))));
             }return dp[id][mask];
          }
          int get(String no,int id){
            return no.charAt(id)-'0';
          }
          long solve(long n){
             long ans=0;
             int length=String.valueOf(n).length();
             ref();
             long A[]=rec1(0,0,length);
             ans=add(ans,A[1]);
             ref();
             A=rec2(0,0,length,false,String.valueOf(n));
             ans=add(ans,A[1]);
             return ans;
          }
          void ref(){
            for(int i=0;i<20;i++){
              for(int j=0;j<1024;j++)dp[i][j][0]=dp[i][j][1]=-1;
            }
          }
          public void solve(int testNumber, InputReader in, PrintWriter out) {
            pre();
            l=in.nextLong();r=in.nextLong();
            k=in.nextInt();
            long A=solve(r);
            long B=solve(l-1);
            out.print(sub(A,B));  
          }
          
//      int[] radixSort(int[] f){ return radixSort(f, f.length); }
//    	int[] radixSort(int[] f, int n)
//    	{
//    		int[] to = new int[n];
//    		{
//    			int[] b = new int[65537];
//    			for(int i = 0;i < n;i++)b[1+(f[i]&0xffff)]++;
//    			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
//    			for(int i = 0;i < n;i++){
//                             to[b[f[i]&0xffff]++] = f[i];
//                            }
//    			int[] d = f; f = to;to = d;
//    		}
//    		{
//    			int[] b = new int[65537];
//    			for(int i = 0;i < n;i++)b[1+(f[i]>>>16)]++;
//    			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
//    			for(int i = 0;i < n;i++)to[b[f[i]>>>16]++] = f[i];
//    			int[] d = f; f = to;to = d;
//    		}
//    		return f;
//    	}
    
       }
 
        
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;
        public InputReader(InputStream stream) throws IOException{
            br = new BufferedReader(new InputStreamReader(stream));
//            br = new BufferedReader(new FileReader("G:\\i.in"));
            st = null;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}