分数: 500 点
问题陈述
给你一个字符串 S 由数字组成。
一个字符串 T 被称为 1122 字符串 如果满足以下所有条件。 (定义与问题C中的相同。)
- T 是由数字组成的非空字符串。
- |T| 是偶数,其中 |T| 表示字符串的长度 T.
- 所有字符来自 1-st 通过 \frac{|T|}2- 第一个字符 T 是相同的数字。
- 所有字符来自 (\frac{|T|}2+1)-th 通过 |T|- 第一个字符 T 是相同的数字。
- 添加 1 到数字 1-st 字符 T 给出的数字 |T|- 第一个字符。
例如, 1122, 01,和 444555 是 1122 个字符串,但是 1222 和 90 不是 1122 个字符串。
求模数 998244353,属于 (不一定连续)子序列 of S 是 1122 个字符串。
如果从不同位置提取两个子序列,即使它们与字符串相同,也会单独计数。
约束
- S 是由长度介于 1 和 10^6,包括在内。
输入
输入由标准输入按以下格式给出:
S
输出
输出数字,模数 998244353,子序列 S 是 1122 个字符串。
示例输入 1
1122
示例输出 1
5
以下五个子序列满足条件。
12摘自 1-st 和 3-rd 字符 S12摘自 1-st 和 4第一个字符 S12摘自 2-nd 和 3-rd 字符 S12摘自 2-nd 和 4第一个字符 S1122摘自 1-st 通过 4第一个字符 S
因此,输出 5.
请注意,如果从不同位置提取两个子序列,即使它们与字符串相同,也会单独计数。
示例输入 2
2025
示例输出 2
0
可能不存在 1122 字符串的子序列。
示例输入 3
0777468889971
示例输出 3
30