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.*;
import java.math.BigInteger;

public class E {

	static long cnt[][][][][];
	static long memo[][][][][];
	static int[] a, b;
	static int k;
	static final int MOD = 998244353;
	static long[] pow;

	static long dp(int less, int greater, int taken, int msk, int pos) {

		if (pos == b.length)
			return 0;

		if (memo[less][greater][taken][msk][pos] != -1)
			return memo[less][greater][taken][msk][pos];

		long ans = 0;

		int s = greater == 1 ? 0 : a[pos], e = less == 1 ? 9 : b[pos];

		for (int i = s; i <= e; i++) {

			ans = add(ans, add(
					mult(mult(i, pow[pos]), count(less | (i < e ? 1 : 0), greater | (i > s ? 1 : 0),
							taken | (i != 0 ? 1 : 0), (taken | (i != 0 ? 1 : 0)) == 1 ? msk | (1 << i) : 0, pos + 1)

					), dp(less | (i < e ? 1 : 0), greater | (i > s ? 1 : 0), taken | (i != 0 ? 1 : 0),
							(taken | (i != 0 ? 1 : 0)) == 1 ? msk | (1 << i) : 0, pos + 1)));

		}
		

		return memo[less][greater][taken][msk][pos] = ans;

	}

	static void init(String l, String r) {

		int sz = r.length();

		pow = new long[sz];

		long curr = 1;

		for (int i = sz - 1; i >= 0; i--, curr = mult(10l, curr))
			pow[i] = curr;

		a = new int[sz];
		b = new int[sz];

		for (int i = 0; i < sz; i++)
			b[i] = r.charAt(i) - '0';

		for (int i = r.length() - l.length(); i < sz; i++)
			a[i] = l.charAt(i - r.length() + l.length()) - '0';
		
		memo = new long[2][2][2][1 << 10 | 1][sz];
		cnt = new long[2][2][2][1 << 10 | 1][sz];


		for (long[][][][] x : memo)
			for (long[][][] xx : x)
				for (long[][] xxx : xx)
					for (long[] xxxx : xxx)
						Arrays.fill(xxxx, -1);

		for (long[][][][] x : cnt)
			for (long[][][] xx : x)
				for (long[][] xxx : xx)
					for (long[] xxxx : xxx)
						Arrays.fill(xxxx, -1);

		//count(0, 0, 0, 0, 0);

	}

	static long count(int less, int greater, int taken, int msk, int pos) {
		if (pos == b.length)
			return Integer.bitCount(msk) <= k ? 1 : 0;

		if (cnt[less][greater][taken][msk][pos] != -1)
			return cnt[less][greater][taken][msk][pos];

		long ans = 0;

		int s = greater == 1 ? 0 : a[pos], e = less == 1 ? 9 : b[pos];

		for (int i = s; i <= e; i++)
			ans += count(less | (i < e ? 1 : 0), greater | (i > s ? 1 : 0), taken | (i != 0 ? 1 : 0),
					(taken | (i != 0 ? 1 : 0)) == 1 ? msk | (1 << i) : 0, pos + 1);

		return cnt[less][greater][taken][msk][pos] = ans;

	}

	static long add(long x, long y) {
		long ans = (1l * x + 1l * y) % MOD;
		return  ans;
	}

	static long mult(long x, long y) {
		if(x > (1e18)/y)
			return  (new BigInteger(x+"").multiply(new BigInteger(y+""))).mod(new BigInteger(MOD+"")).longValue();
		
		return (1l * x * y ) % MOD ;
 	}

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		String l = sc.next(), r = sc.next();
		k = sc.nextInt();

		init(l, r);
		
		out.println(dp(0, 0, 0, 0, 0));
		
		
		sc.close();
		out.flush();
		out.close();

	}

}