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.Arrays;
import java.util.Scanner;

public class P1073E
{
	static int mod = 998244353;
	static long[] pow10mod;
	static int k;
	static int[] num;
	static int[][][] dp, dpWays;
	public static void main(String[] args)
	{
		pow10mod = new long[30];
		pow10mod[0] = 1;
		for (int i = 1; i < pow10mod.length; i++)
			pow10mod[i] = 10*pow10mod[i-1] % mod;
		Scanner scan = new Scanner(System.in);
		long a = scan.nextLong();
		long b = scan.nextLong();
		k = scan.nextInt();
		System.out.println((cnt(b) - cnt(a-1) + mod) % mod);
	}
	private static long cnt(long n)
	{
		char[] ch = (""+n).toCharArray();
		num = new int[ch.length];
		for (int i = 0; i < ch.length; i++)
			num[i] = ch[i]-'0';
		
		dp = new int[2][num.length][1 << 10];
		for (int[][] a : dp)
			for (int[] b : a)
				Arrays.fill(b, -1);
		dpWays = new int[2][num.length][1 << 10];
		for (int[][] a : dpWays)
			for (int[] b : a)
				Arrays.fill(b, -1);
		
		return go(0, 0, 0, true);
	}
	private static int go(int started, int ind, int mask, boolean bounded)
	{
		if (ind == num.length)
			return 0;
		if (!bounded && dp[started][ind][mask] >= 0)
			return dp[started][ind][mask];
		
		long ans = 0;
		int b = bounded ? num[ind] : 9;
		for (int i = 0; i <= b; i++)
		{
			long mult = i*pow10mod[num.length-ind-1] % mod;
			ans += mult*ways(started == 1 || i > 0 ? 1 : 0, ind+1, started == 0 && i == 0 ? mask : mask | (1 << i), bounded && i == b);
			ans += go(started == 1 || i > 0 ? 1 : 0, ind+1, started == 0 && i == 0 ? mask : mask | (1 << i), bounded && i == b);
		}
		
		if (!bounded)
			dp[started][ind][mask] = (int)(ans % mod);
		return (int)(ans % mod);
	}
	private static int ways(int started, int ind, int mask, boolean bounded)
	{
		if (ind == num.length)
			return Integer.bitCount(mask) <= k ? 1 : 0;
		if (!bounded && dpWays[started][ind][mask] >= 0)
			return dpWays[started][ind][mask];
		
		long ans = 0;
		int b = bounded ? num[ind] : 9;
		for (int i = 0; i <= b; i++)
			ans += ways(started == 1 || i > 0 ? 1 : 0, ind+1, started == 0 && i == 0 ? mask : mask | (1 << i), bounded && i == b);
		
		if (!bounded)
			dpWays[started][ind][mask] = (int)(ans % mod);
		return (int)(ans % mod);
	}
}
