AT_abc433_f.[ABC433F] 1122 Subsequence 2

给定一个由数字组成的字符串 $S$。

一个字符串 $T$ 被称为 1122-字符串，当且仅当它满足以下所有条件（定义同问题 C）：

• $T$ 是一个非空的数字字符串；
• $|T|$ 是偶数，其中 $|T|$ 表示字符串 $T$ 的长度；
• $T$ 的第 $1$ 到第 $\frac{|T|}2$ 个字符都是相同的数字；
• $T$ 的第 $(\frac{|T|}2+1)$ 到第 $|T|$ 个字符都是相同的数字；
• 将 $T$ 的第 $1$ 个字符代表的数字加 $1$，恰好等于 $T$ 的第 $|T|$ 个字符代表的数字。

例如，1122、01 和 444555 都是 1122-字符串，而 1222 和 90 不是 1122-字符串。

请计算 $S$ 的**（不一定连续的）子序列**中有多少个是 1122-字符串。由于答案可能很大，请对 $998244353$ 取模。

两个子序列只要抽取的位置不同，即使内容相同，也要分别计数。

输入由标准输入给出，格式如下：

$S$

输出 $S$ 中所有 1122-字符串子序列的个数，对 $998244353$ 取模。

样例解释 1

以下五个子序列满足条件：

• 从 $S$ 的第 $1$ 和第 $3$ 个字符抽取得到的 12
• 从 $S$ 的第 $1$ 和第 $4$ 个字符抽取得到的 12
• 从 $S$ 的第 $2$ 和第 $3$ 个字符抽取得到的 12
• 从 $S$ 的第 $2$ 和第 $4$ 个字符抽取得到的 12
• 从 $S$ 的第 $1$ 到第 $4$ 个字符依次抽取得到的 1122

因此输出 $5$。

注意：只要抽取位置不同，即使形成的子序列字符串相同，也分别计数。

样例解释 2

可能没有任何子序列是 1122-字符串。

数据范围

• $S$ 是一个长度在 $1$ 到 $10^6$ 之间的数字字符串。

由 ChatGPT 5 翻译