[R59F]数汉堡 - 代码源竞赛平台

时空限制

2S/512M

题目描述

apiadu 面前摆着 jiangly 做的 $n$ 个汉堡，编号为 $1$ 到 $n$。

由于 jiangly 与数字之间有着神奇的联系，每个汉堡的美味程度并不相同。jiangly 手中有一个喜欢的数字串 $t$。对于编号为 $i$ 的汉堡，我们将编号 $i$ 的各位数字从前往后拼接得到字符串 $s$。

汉堡的美味程度定义如下：

• 如果数字串 $t$ 是 $s$ 的子序列（不一定连续），则该汉堡的美味程度为 $1$。
• 否则，该汉堡的美味程度为 $0$。

apiadu 想知道吃下所有 $n$ 个汉堡后的美味度之和是多少。由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

格式

输入格式

第一行一个整数 $n$，表示汉堡的数量。

第二行一个数字串 $t$，表示 jiangly 喜欢的数字串。

输出格式

一个整数，表示所有汉堡美味度之和对 $998244353$ 取模的结果。

样例

样例输入 #1

1000
16

样例输出 #1

28

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n \leq$
$1$	$20$	$10^7$
$2$	$80$	$10^{2000}$

对于 $100\%$ 的数据，$|t| \le a$，其中 $a$ 是 $n$ 的位数。且数字串 $t$ 中不包含数字 0。$n$ 对应的字符串不含前导零。