问题 R: 会笑的数

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:9 解决:5

题目描述



如果有一个 $N$ 位的十进制正整数 $S$ 和一个 $M$ 位的十进制正整数 $T$ $(M<=N)$,$S$和 $T$ 可以有前导 $0$;

将S从低位到高位编号为 $0,1,...,N-1$,对于任意满足 $l<=r$并且 $r-l+1=M$的 $l,r$ ,取出 $S$中编号位于 $[l,r]$之间(即 $l,l-1,...,r+1,r$)的数,按原来的顺序组成一个新的十进制正整数,如果它们与T都不相等,我们称 $S$是一个对 $T$笑的数;
例如:如果取 $S=9876543210, T=876$ ,此时$S$就不是一个对$T$笑的数 ,因为存在 $l=6, r=8$($r-l+1=3$且得到的数为 $876$) 满足条件;
如果取$S=9876543210,T=78$,此时 $S$就是一个对 $T$ 笑的数,因为找不到 $l, r$ 使得到得新数字与 $T$ 相等;
现在已知 $S$的位数 $N$和数字 $T$,求对 $T$笑的数 $S$有多少种取值的方案,结果对 $998244353$取模。

输入

输入包括两行:
第一行输入两个整数 $N,M$,($N<=500,M<=N$)$N$表示 $S$的位数,$M$表示 $T$的位数;
第二行输入一个位数为 $M$的十进制整数 $ T $;

输出

输出一个整数:
表示对 $T$笑的数 $S$取值的方案数,结果对 $998244353$取模。

样例输入 复制

5 1
1

样例输出 复制

59049