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.
// package CodeForces;

import java.io.*;
import java.util.*;

public class Problem_1073E {
//	static int solve()
//	{
//		
//	}
	static Pair dp(int idx,int msk,int f,String s)
	{
		if(idx==n)
		{
//			System.out.println(s);
			return new Pair(0, 1);
		}
		if(memo[idx][msk][f].ans!=-1)
		{
//			System.out.println("memo "+s);
			return memo[idx][msk][f];
		}
		int tmpk=Integer.bitCount(msk);
		long digit=(long)Math.pow(10, n-idx-1);
		long ans=0;
//		System.out.println(tmpk+" "+k);
		long count=0;
		if(tmpk<k)
		{
			if(msk==0)
			{
				Pair p=dp(idx+1,msk,0,s+0);							
				long tmp=(((digit*0)%mod)*p.c)%mod+p.ans;
				ans+=(tmp%mod);
				ans%=mod;
				count+=p.c;
				count%=mod;
			}
			else
			{
				int i=0;
				if(f==1)
				{	
					if(i<Integer.parseInt(r[idx]+""))
					{
						Pair p=dp(idx+1,msk|(1<<i),0,s+i);							
						long tmp=(((digit*i)%mod)*p.c)%mod+p.ans;
						ans+=(tmp%mod);
						ans%=mod;
						count+=p.c;
						count%=mod;
					}
					else if(i==Integer.parseInt(r[idx]+""))
					{
						Pair p=dp(idx+1,msk|(1<<i),1,s+i);
						long tmp=(((digit*i)%mod)*p.c)%mod+p.ans;
						ans+=(tmp%mod);
						ans%=mod;
						count+=p.c;
						count%=mod;
					}
				}
				else
				{
					Pair p=dp(idx+1,msk|(1<<i),0,s+i);
					long tmp=(((digit*i)%mod)*p.c)%mod+p.ans;
					ans+=(tmp%mod);
					ans%=mod;
					count+=p.c;
					count%=mod;
				}
			}
			for(int i=1;i<10;i++)
			{
				if(f==1)
				{	
					if(i<Integer.parseInt(r[idx]+""))
					{
						Pair p=dp(idx+1,msk|(1<<i),0,s+i);							
						long tmp=(((digit*i)%mod)*p.c)%mod+p.ans;
						ans+=(tmp%mod);
						ans%=mod;
						count+=p.c;
						count%=mod;
					}
					else if(i==Integer.parseInt(r[idx]+""))
					{
						Pair p=dp(idx+1,msk|(1<<i),1,s+i);
						long tmp=(((digit*i)%mod)*p.c)%mod+p.ans;
						ans+=(tmp%mod);
						ans%=mod;
						count+=p.c;
						count%=mod;
					}
				}
				else
				{
					Pair p=dp(idx+1,msk|(1<<i),0,s+i);
					long tmp=(((digit*i)%mod)*p.c)%mod+p.ans;
					ans+=(tmp%mod);
					ans%=mod;
					count+=p.c;
					count%=mod;
				}
			}
		}
		else
		{
			char[] c=Integer.toBinaryString(msk).toCharArray();
			int j=c.length-1;
			for(int i=0;i<10 && j>=0;i++,j--)
			{
				if(c[j]=='1')
				{
					if(f==1)
					{	
						if(i<Integer.parseInt(r[idx]+""))
						{
							Pair p=dp(idx+1,msk|(1<<i),0,s+i);
							long tmp=(((digit*i)%mod)*p.c)%mod+p.ans;
							ans+=(tmp%mod);
							count+=p.c;
							count%=mod;
						}
						else if(i==Integer.parseInt(r[idx]+""))
						{
							Pair p=dp(idx+1,msk|(1<<i),1,s+i);
							long tmp=(((digit*i)%mod)*p.c)%mod+p.ans;
							ans+=(tmp%mod);
							count+=p.c;
							count%=mod;
						}
						ans%=mod;
					}
					else
					{
						Pair p=dp(idx+1,msk|(1<<i),0,s+i);
						long tmp=(((digit*i)%mod)*p.c)%mod+p.ans;
						ans+=(tmp%mod);
						ans%=mod;
						count+=p.c;
						count%=mod;
					}
				}
			}
		}
		return memo[idx][msk][f]=new Pair(ans%mod, count%mod);
	}
	static class Pair
	{
		long c;long ans;
		public Pair(long ans,long count) {
			// TODO Auto-generated constructor stub
			c=count;this.ans=ans;
		}
	}
	static int n,k;
	static Pair memo[][][];
	static long mod=998244353;
	static char l[],r[];
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st=new StringTokenizer(sc.nextLine());
		long ll=Long.parseLong(st.nextToken())-1;
		l=(ll+"").toCharArray();r=st.nextToken().toCharArray();
		k=Integer.parseInt(st.nextToken());
		n=r.length;
		memo=new Pair[n][2048][2];
		for(int i=0;i<n;i++)
			for(int j=0;j<2048;j++)
				for(int k=0;k<2;k++)
					memo[i][j][k]=new Pair(-1,1);
		long rans=dp(0,0,1,"").ans%mod;
		r=l;
		n=l.length;
		for(int i=0;i<n;i++)
			for(int j=0;j<2048;j++)
				for(int k=0;k<2;k++)
					memo[i][j][k]=new Pair(-1,1);
		long lans=dp(0,0,1,"").ans%mod;
		long ans=rans-lans;
//		System.out.println(lans+" "+rans);
		if(ans<0)
			ans+=mod;
		pw.print(ans);
		pw.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();
		}

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

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

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

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

		boolean hasnext() throws IOException {
			return br.ready();
		}

	}
}
