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 Main2{
	static char[]cur;
	static long[][][][]memoCnt,memoAns;
	static int mod=998244353,k;
	static long[]pow;
	static long dp(int smaller,int started,int i,int msk,int curp) {
		if(i==cur.length)return Integer.bitCount(msk)<=k?1:0;
		if(memoCnt[smaller][started][i][msk]!=-1)return memoCnt[smaller][started][i][msk];
		long ans=0,cnt=0;
		if(started==0) {
			cnt=dp(1, started, i+1, msk,curp-1);
			ans=(ans+(i+1==cur.length?0:memoAns[1][started][i+1][msk]))%mod;
			int d=1;
			for(;d<((smaller==0)?(cur[i]-'0'):10);d++) {
				cnt=(cnt+dp(1, 1, i+1, msk|(1<<d),curp-1))%mod;
				long val=(pow[curp]*d)%mod;
				ans=(ans+val*dp(1, 1, i+1, msk|(1<<d),curp-1))%mod;
				ans=(ans+(i+1==cur.length?0:memoAns[1][1][i+1][msk|(1<<d)]))%mod;
			}
			if(d==(cur[i]-'0')) {
				cnt=(cnt+dp(0, 1, i+1, msk|(1<<d),curp-1))%mod;
				long val=(pow[curp]*d)%mod;
				ans=(ans+val*dp(0, 1, i+1, msk|(1<<d),curp-1))%mod;
				ans=(ans+(i+1==cur.length?0:memoAns[0][1][i+1][msk|(1<<d)]))%mod;
			}
			memoAns[smaller][started][i][msk]=ans;
			return memoCnt[smaller][started][i][msk]=cnt;
		}
		if(smaller==0) {
			int d=0;
			for(;d<(cur[i]-'0');d++) {
				cnt=(cnt+dp(1, 1, i+1, msk|(1<<d),curp-1))%mod;
				long val=(pow[curp]*d)%mod;
				ans=(ans+val*dp(1, 1, i+1, msk|(1<<d),curp-1))%mod;
				ans=(ans+(i+1==cur.length?0:memoAns[1][1][i+1][msk|(1<<d)]))%mod;
			}
			cnt=(cnt+dp(0, 1, i+1, msk|(1<<d),curp-1))%mod;
			long val=(pow[curp]*d)%mod;
			ans=(ans+val*dp(0, 1, i+1, msk|(1<<d),curp-1))%mod;
			ans=(ans+(i+1==cur.length?0:memoAns[0][1][i+1][msk|(1<<d)]))%mod;
			memoAns[smaller][started][i][msk]=ans;
			return memoCnt[smaller][started][i][msk]=cnt;
		}
		for(int d=0;d<=9;d++) {
			cnt=(cnt+dp(1, 1, i+1, msk|(1<<d),curp-1))%mod;
			long val=(pow[curp]*d)%mod;
			ans=(ans+val*dp(1, 1, i+1, msk|(1<<d),curp-1))%mod;
			ans=(ans+(i+1==cur.length?0:memoAns[1][1][i+1][msk|(1<<d)]))%mod;
		}
		memoAns[smaller][started][i][msk]=ans;
		return memoCnt[smaller][started][i][msk]=cnt;
	}
	static void main() throws Exception{
		pow=new long[20];
		pow[0]=1;
		for(int i=1;i<20;i++) {
			pow[i]=(pow[i-1]*10)%mod;
		}
		long l=sc.nextLong()-1,r=sc.nextLong();
		k=sc.nextInt();
		cur=Long.toString(r).toCharArray();
		memoCnt=new long[2][2][cur.length][1<<10];
		memoAns=new long[2][2][cur.length][1<<10];
		for(int i=0;i<2;i++) {
			for(int j=0;j<2;j++) {
				for(int o=0;o<cur.length;o++) {
					for(int z=0;z<1<<10;z++) {
						memoCnt[i][j][o][z]=-1;
						memoAns[i][j][o][z]=0;
					}
				}
			}
		}
		dp(0, 0, 0, 0, cur.length-1);
		long ans=memoAns[0][0][0][0];
		cur=Long.toString(l).toCharArray();
		memoCnt=new long[2][2][cur.length][1<<10];
		memoAns=new long[2][2][cur.length][1<<10];
		for(int i=0;i<2;i++) {
			for(int j=0;j<2;j++) {
				for(int o=0;o<cur.length;o++) {
					for(int z=0;z<1<<10;z++) {
						memoCnt[i][j][o][z]=-1;
						memoAns[i][j][o][z]=0;
					}
				}
			}
		}
		dp(0, 0, 0, 0, cur.length-1);
		ans=(ans+mod-memoAns[0][0][0][0])%mod;
		pw.println(ans);
    }
    public static void main(String[] args) throws Exception{
    	sc=new MScanner(System.in);
    	pw = new PrintWriter(System.out);
        int tc=1;
//        tc=sc.nextInt();
        for(int i=1;i<=tc;i++) {
//            pw.printf("Case #%d:", i);
            main();
        }
        pw.flush();
    }
    static PrintWriter pw;
    static MScanner sc;
    static class MScanner {
        StringTokenizer st;
        BufferedReader br;
        public MScanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }
     
        public MScanner(String file) throws Exception {
            br = new BufferedReader(new FileReader(file));
        }
     
        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        public int[] intArr(int n) throws IOException {
            int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
            return in;
        }
        public long[] longArr(int n) throws IOException {
            long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            return in;
        }
        public int[] intSortedArr(int n) throws IOException {
            int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
            shuffle(in);
            Arrays.sort(in);
            return in;
        }
        public long[] longSortedArr(int n) throws IOException {
            long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            shuffle(in);
            Arrays.sort(in);
            return in;
        }
        public Integer[] IntegerArr(int n) throws IOException {
            Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
            return in;
        }
        public Long[] LongArr(int n) throws IOException {
            Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
            return in;
        }
        public String nextLine() throws IOException {
            return br.readLine();
        }
     
        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
     
        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
     
        public char nextChar() throws IOException {
            return next().charAt(0);
        }
     
        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }
     
        public boolean ready() throws IOException {
            return br.ready();
        }
     
        public void waitForInput() throws InterruptedException {
            Thread.sleep(3000);
        }
        
    }
    static void sort(int[]in) {
    	shuffle(in);
        Arrays.sort(in);
    }
    static void sort(long[]in) {
    	shuffle(in);
        Arrays.sort(in);
    }
    static void shuffle(int[]in) {
        for(int i=0;i<in.length;i++) {
            int idx=(int)(Math.random()*in.length);
            int tmp=in[i];
            in[i]=in[idx];
            in[idx]=tmp;
        }
    }
    static void shuffle(long[]in) {
        for(int i=0;i<in.length;i++) {
            int idx=(int)(Math.random()*in.length);
            long tmp=in[i];
            in[i]=in[idx];
            in[idx]=tmp;
        }
    }
}