该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

$\hspace{15pt}$在浩瀚的欧几里得星系，旅行者（Traveler）在一个废弃的科尔瓦克斯（Korvax）空间站深处，发现了一座通往“阿特拉斯（Atlas）”核心的传送门。

$\hspace{15pt}$传送门的终端上显示着一串极长的远古加密数字串 $S$。根据旅行者多周目的经验，若要激活传送门且不惊动护卫（Sentinels），不能直接输入这串数字，而是需要将其切分成恰好 $K$ 个非空的连续数据段。

$\hspace{15pt}$这 $K$ 个数据段会被传送门转化为十进制的脉冲能量。设切分出的 $K$ 个段分别为 $S_1, S_2, \dots, S_K$，那么它们产生的总能量为 $V = \text{Value}(S_1) + \text{Value}(S_2) + \dots + \text{Value}(S_K)$。 (注：如果某段数据包含前导零，则按常规数字计算，例如段 "04" 的能量为 $4$，"00" 的能量为 $0$)。

$\hspace{15pt}$阿特拉斯接口是一个极具对称与和谐的实体，只有当总能量 $V$ 能够与它产生共鸣——即 $V$ 是 $9$ 的倍数 时，传送门才会开启。

$\hspace{15pt}$旅行者想知道，在所有可能的切分方案中，有多少种方案能成功开启传送门？由于方案数可能极大，请将结果对 $998244353$ 取模。

$\hspace{15pt}$给定一个长度为 $N$ 的纯数字字符串 $S$ 和一个正整数 $K$。

$\hspace{15pt}$求将 $S$ 划分为 $K$ 个非空连续子串，且这 $K$ 个子串对应的十进制数值之和是 $9$ 的倍数的方案数。 答案对 $998244353$ 取模。

Input

$\hspace{15pt}$第一行包含两个正整数 $N$ 和 $K$ ($1 \le K \le N \le 2 \times 10^5$)，分别表示字符串的长度和需要切分的数据段数。

$\hspace{15pt}$第二行包含一个长度为 $N$ 的数字字符串 $S$。

Output

$\hspace{15pt}$输出一行一个整数，表示合法的切分方案数对 $998244353$ 取模后的结果。

Example

3 2
126

2

4 2
1234

0

6 3
999999

10

Note

$\hspace{15pt}$对于样例 1，将 "126" 切分成 2 段，有以下两种方案：

1. "1" 和 "26"：能量和为 $1 + 26 = 27$，是 $9$ 的倍数。
2. "12" 和 "6"：能量和为 $12 + 6 = 18$，也是 $9$ 的倍数。 $\hspace{15pt}$因此有 2 种方案。

$\hspace{15pt}$对于样例 2，将 "1234" 切分成 2 段，不论怎么切，能量和（$235, 46, 127$）都不是 $9$ 的倍数，因此方案数为 0。