时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的数字串 $S$ 和一个整数 $k$。

你需要在 $S$ 的 $n-1$ 个空隙中插入恰好 $k$ 个加号 +，将其变成一个数学表达式。

例如，对于 $S = 1234$ 和 $k=1$，你可以得到三种表达式：1+234、12+34 和 123+4。

你的任务是计算所有可能的表达式的结果之和，并对 $998244353$ 取模。

注意：表达式中的数字可以包含前导零（例如，01+2 的计算结果是 $3$）。

格式

输入格式

第一行包含两个整数 $n, k$，分别表示数字串的长度和需要插入的加号数量。

第二行包含一个长度为 $n$ 的数字串 $S$。

输出格式

输出一个整数，表示所有表达式结果的总和，对 $998244353$ 取模。

样例

样例输入 #1

4 1
1234

样例输出 #1

408

样例解释 #1

数字串 $S = 1234$，长度 $n=4$，需要插入 $k=1$ 个加号。 共有 $n-1 = 3$ 个可以插入加号的空隙。我们需要选择其中一个。

所有可能的插入方式如下：

1. 在第 1 个空隙插入：1+234。结果为 $1 + 234 = 235$。
2. 在第 2 个空隙插入：12+34。结果为 $12 + 34 = 46$。
3. 在第 3 个空隙插入：123+4。结果为 $123 + 4 = 127$。

这些结果的总和是 $235 + 46 + 127 = 408$。

数据规模

对于 $30\%$ 的数据，$1\leq n \leq 10$。

对于 $50\%$ 的数据，$1 \leq n \leq 2000$.

对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^5$，$0 \leq k < n$，$0 \leq S_i \leq 9$。