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 H {

	static char[] s;
	static int n, k;
	static long[] pow;
	static int MOD = 998244353;

	static int solve(long r) {
		s = (r + "").toCharArray();
		n = s.length;
		memo=new pair[2][n][1100];
		
		return dp(0, 0, 0, 0).v;
	}
	static pair[][][]memo;
	static class pair
	{
		int v,cnt;
		pair(int a,int b){
			v=a;
			cnt=b;
		}
	}
	static pair dp(int idx, int less, int dis, int msk) {
		
		
		
		if(idx==n)
			return new pair(0,1);
		if(memo[less][idx][msk]!=null)
			return memo[less][idx][msk];
		long ans = 0;
		long cnt=0;
		int up = less == 1 ? 9 : s[idx] - '0';
		for (int d = 0; d <= up; d++) {
			int newLess = less == 1 ? 1 : d < s[idx] - '0' ? 1 : 0;
			int newDis =dis;
			if((msk & 1 << d) == 0  && (msk>1 || d>0))
				newDis++;
			if(newDis>k)
				continue;
			
			long x=d*pow[n-1-idx]%MOD;
		    int newMsk=msk;
		    if(newDis==dis+1)
		        newMsk|=1<<d;
			pair p=dp(idx + 1, newLess, newDis,newMsk);
			ans = ans +p.v ;
			
			ans %= MOD;
			long y=x*p.cnt%MOD;
			ans+=y;
			ans%=MOD;
			cnt+=p.cnt;
			cnt%=MOD;
		}

		return memo[less][idx][msk]=new pair((int) ans,(int)cnt);

	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		long l=sc.nextLong(),r=sc.nextLong();
		k=sc.nextInt();
		
		pow=new long [20];
		pow[0]=1;
		for(int i=1;i<pow.length;i++)
			pow[i]=10*pow[i-1]%MOD;
		long ans=(solve(r)-solve(l-1));
		if(ans<0)
			ans+=MOD;
		out.println(ans);
		out.close();
	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

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

		String nextLine() throws IOException {
			return br.readLine();
		}

		double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		long nextLong() throws IOException {
			return Long.parseLong(next());
		}
	}
}