数位

枚举 $S=a_1+a_2+\dots+a_k$。通过容斥发现合法方案数应当是：

$$\sum_{i=0}^k (-1)^i\cdot\dbinom ki\cdot \dbinom{S-k(L-1)-i(R-L+1)-1}{k-1}$$

需要注意的是最后一个组合数可能上面小于下面导致这玩意是 $0$，也就是这玩意不完全是关于 $S$ 的 $k$ 次多项式。

我们可以通过枚举 $k$，钦定 $S\in[i(R+1)+(k-i)L,kR]$。这样子这个组合数显然的关于 $S$ 的 $k-1$ 次多项式。解决这个问题是容易的。

具体的，假设 $n=\lg kR$，通过差分我们只需要计算一边。定义 $f_{i,j,o,k}$ 表示当前只考虑 $S[i,n]$ 且 $S_i=j$，$S[i,n]$ 是否等于 $kR[i,n]$，满足这样条件 $S[i,n]$ 的 $k$ 次方和。

转移可以通过二项式定理拆开。具体的转移见代码。

算一下复杂度，假设 $B=10$，复杂度是 $\mathcal O(nk^3B^2)$。剪一下枝，写完发现有 $92$ 分的样子。

考虑怎么过掉最后两个点，你发现 $o=1$ 有用情况很少，不用管。只需要 $o=0$ 之间的贡献即可。

不难发现 $o=0$ 收到上一层 $o=0$ 的是贡献是一个 $j$ 的后缀，通过后缀和可以丢掉一个 $B$。

时间复杂度是 $\mathcal O(nk^3B)$。

为了卡常需要把主要 dp 数组全部换成 int 以加快速度，在计数题效果很明显。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1005;
const int MR=55;
const int MOD=998244353;
ll pw[11][MAXN*MR],fac[MR],inf[MR],c[MR][MR];
struct Big_Int{
int a[MAXN+5];
int& operator [](int x){return a[x];}
Big_Int(int x=0){
	memset(a,0,sizeof(a));
	for(int i=0;i<=10;i++) a[i]=x%10,x/=10;
}
}L,R;int k;
Big_Int read(){
	Big_Int re;int n=0;char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9') re[n++]=ch-'0',ch=getchar();
	reverse(re.a,re.a+n);
	return re;
}
Big_Int operator +(Big_Int x,Big_Int y){
	for(int i=0;i<MAXN;i++){
		x[i]+=y[i];
		if(x[i]>=10) x[i]-=10,x[i+1]++;
	}
	return x;
}
Big_Int operator -(Big_Int x,Big_Int y){
	for(int i=0;i<MAXN;i++){
		x[i]-=y[i];
		if(x[i]<0) x[i]+=10,x[i+1]--;
	}
	return x;
}
bool operator >=(Big_Int x,Big_Int y){
	for(int i=MAXN;i>=0;i--) if(x[i]!=y[i]) return x[i]>y[i];
	return true;
}
Big_Int operator *(Big_Int x,int y){
	for(int i=0;i<MAXN;i++) x[i]*=y;
	for(int i=0;i<MAXN;i++) x[i+1]+=x[i]/10,x[i]%=10;
	return x;
}
int operator %(Big_Int x,int y){
	int ans=0;
	for(int i=MAXN-1;i>=0;i--) ans=(10ll*ans+x[i])%y;
	return ans;
}
ll ksm(ll a,int b){ll r=1;while(b){if(b&1)r=r*a%MOD;a=a*a%MOD,b>>=1;}return r;}
void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}
int f[MR],g[MR];// all possible S, calculate the sum of S^k
ll C(int x,int y){return fac[y]*inf[x]%MOD*inf[y-x]%MOD;}
void solve(Big_Int R,int *ans){
	static int f[MAXN][10][MR][2],g[MAXN][10][MR];
	ans[0]=1;
	memset(f,0,sizeof(f));memset(g,0,sizeof(g));
	int n=MAXN;
	while(n&&!R[n]) n--;
	for(int i=n+1;i>=0;i--){
		f[i][9][0][i==n+1]++;ans[0]--;
		for(int j=0;j<=9;j++) for(int t=0;t<k;t++) if(i&&f[i][j][t][1]){
			int lim=min(j,R[i-1]);
			for(int c=0;c<=lim;c++) for(int p=0;p+t<k;p++)
				add(f[i-1][c][p+t][c==R[i-1]],
				f[i][j][t][1]*pw[10][(i-1)*p]%MOD*pw[c][p]%MOD*C(p,p+t)%MOD);
		}
		for(int c=0;c<=9;c++) for(int t=0;t<k;t++){
			for(int p=0;p<=t;p++) add(f[i][c][t][0],
				C(p,t)*g[i+1][c][t-p]%MOD*pw[10][i*p]%MOD*pw[c][p]%MOD);
		}
		for(int t=0;t<k;t++){
			g[i][9][t]=f[i][9][t][0];
			for(int c=8;c>=0;c--) g[i][c][t]=(g[i][c+1][t]+f[i][c][t][0])%MOD;
		}
	}
	for(int i=0;i<=9;i++) for(int o:{0,1}) for(int t=0;t<k;t++)
		add(ans[t],f[0][i][t][o]);
}
int main(){
	// freopen("digit.in","r",stdin);
	// freopen("digit.out","w",stdout);
	L=read();R=read();k=read()%MOD;
	for(int i=0;i<=10;i++){
		pw[i][0]=1;
		for(int j=1;j<MAXN*MR;j++) pw[i][j]=pw[i][j-1]*i%MOD;
	}
	fac[0]=inf[0]=1;
	for(int i=1;i<MR;i++) inf[i]=ksm(fac[i]=fac[i-1]*i%MOD,MOD-2);
	int ans=0;
	solve(R*k,f);
	for(int i=0;i<=k;i++)if(R*k>=(R+1)*i+L*(k-i)){
		memset(g,0,sizeof(g));
		solve(L*(k-i)+(R+Big_Int(1))*i-Big_Int(1),g);
		ll x=((L-Big_Int(1))*k+(R-L+Big_Int(1))*i+Big_Int(1))%MOD;
		c[0][0]=1;
		for(int i=1;i<=k-1;i++){
			for(int j=0;j<=i;j++) c[i][j]=((j?c[i-1][j-1]:0)+(MOD-x-(i-1))*c[i-1][j])%MOD;
		}
		int sum=0;
		for(int i=0;i<=k-1;i++) add(sum,inf[k-1]*c[k-1][i]%MOD*(f[i]-g[i]+MOD)%MOD);
		add(ans,fac[k]*inf[i]%MOD*inf[k-i]%MOD*(i&1?MOD-1:1)%MOD*sum%MOD);	
	}
	cout<<ans<<'\n';
	return 0;
}