20021 - Subsequence

给定一个由数字组成的字符串 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 之间的数字字符串。