You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题陈述

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ： "$1$" -> '$A$' "$2$" -> '$B$' ... "$25$" -> '$Y$' "$26$" -> '$Z$' 然而，在解码已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"$2$" 和 "$5$" 与 "$25$"）。 例如，"$11106$" 可以映射为： "$AAJF$" ，将消息分组为 ($1$, $1$, $10$, $6$) "$KJF$" ，将消息分组为 ($11$, $10$, $6$) 消息不能分组为 ($1$, $11$, $06$) ，因为 "$06$" 不是一个合法编码（只有 "$6$" 是合法的）。 注意，可能存在无法解码的字符串。 给你一个只含数字的非空字符串s,请计算并返回解码方法的 总数.如果没有合法的方式解码整个字符串，返回$0$。 答案可能很大 输出对$998244353$取模的结果

输入格式

包含一个字符串 $s$，只包含数字 ( $1 \le |s| \le 10^5$ )

输出格式

输出答案对$998244353$取模的结果

样例1

input

12

output

2

样例2

input

226

output

3

样例解释

对于第一个样例：它可以解码为 "$AB$"（$1$ $2$）或者 "$L$"（$12$） 对于第二个样例：它可以解码为 "$BZ$" ($2$ $26$), "$VF$" ($22$ $6$), 或者 "$BBF$" ($2$ $2$ $6$)

限制与约定

对于 $30\%$ 的数据，$1 \le |s| \le 20$ 。 对于 $100\%$ 的数据，$1 \le |s| \le 10^5$ 。

• 时间限制: $1 s$
• 空间限制: $256 MB$