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 CF1073E {
	int len, num[];
	long solve(long x) {
		if(x == 0) return 0;
		len = 0;
		for(long tmp = x ; tmp > 0 ; tmp /= 10)
			len++;
		num = new int[len];
		for(int i = len - 1 ; i >= 0 ; i--, x /= 10)
			num[i] = (int) (x % 10);
		dp1 = new long[2][len][len + 1][1 << 10];
		dp2 = new long[2][len][len + 1][1 << 10];
		for(int i = 0 ; i < 2 ; i++) {
			for(int j = 0 ; j < len ; j++) {
				for(int k = 0 ; k < len + 1 ; k++) {
					Arrays.fill(dp1[i][j][k], -1);
					Arrays.fill(dp2[i][j][k], -1);
				}
			}
		}
		long res = go1(1, 0, len, 0);
		for(int curlen = 1 ; curlen < len ; curlen++)
			res = (res + go1(0, 0, curlen, 0)) % MOD;
		System.out.println();
		return res;
	}
	long go1(int eq, int at, int curlen, int m) {
		if(at == curlen)
			return 0;
		if(dp1[eq][at][curlen][m] != -1)
			return dp1[eq][at][curlen][m];
		long res = 0;
		for(int digit = 0 ; digit < 10 ; digit++) {
			if(at == 0 && digit == 0) continue;
			int newm = m | (1 << digit);
			if(Integer.bitCount(newm) <= k) {
				long val = (digit * pow10[curlen - at - 1]) % MOD;
				if(eq == 1) {
					if(digit == num[at]) {
						res += (go2(1, at + 1, curlen, newm) * val) % MOD;
						res += go1(1, at + 1, curlen, newm);
						res %= MOD;
					} else if(digit < num[at]) {
						res += (go2(0, at + 1, curlen, newm) * val) % MOD;
						res += go1(0, at + 1, curlen, newm);
						res %= MOD;
					}
				} else {
					res += (go2(0, at + 1, curlen, newm) * val) % MOD;
					res += go1(0, at + 1, curlen, newm);
					res %= MOD;
				}
			}
		}
		dp1[eq][at][curlen][m] = res;
		return res;
	}
	long go2(int eq, int at, int curlen, int m) {
		if(at == curlen)
			return 1;
		if(dp2[eq][at][curlen][m] != -1)
			return dp2[eq][at][curlen][m];
		long res = 0;
		for(int digit = 0 ; digit < 10 ; digit++) {
			if(at == 0 && digit == 0) continue;
			int newm = m | (1 << digit);
			if(Integer.bitCount(newm) <= k) {
				if(eq == 1) {
					if(digit == num[at]) {
						res += go2(1, at + 1, curlen, newm);
						res %= MOD;
					} else if(digit < num[at]) {
						res += go2(0, at + 1, curlen, newm);
						res %= MOD;
					}
				} else {
					res += go2(0, at + 1, curlen, newm);
					res %= MOD;
				}
			}
		}
		dp2[eq][at][curlen][m] = res;
		return res;
	}
	long[] pow10;
	final int MOD = 998_244_353;
	long[][][][] dp2, dp1;
	int k;
	public CF1073E() {
		FS scan = new FS();
		pow10 = new long[19];
		pow10[0] = 1;
		for(int i = 1 ; i < 19 ; i++)
			pow10[i] = (pow10[i - 1] * 10) % MOD;
		long l = scan.nextLong(), r = scan.nextLong();
		k = scan.nextInt();
		long res = (solve(r) - solve(l - 1) + MOD) % MOD;
		System.out.println(res);
	}
	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() {
			while(!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) { e.printStackTrace(); }
			}
			return st.nextToken();
		}
		public int nextInt() { return Integer.parseInt(next()); }
		public long nextLong() { return Long.parseLong(next()); }
	}
	public static void main(String[] args) { new CF1073E(); }
}