← 返回题目列表

AtCoder · abc433_f

I. 1122 子序列 2

中文机器翻译题面 查看原题

分数: 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 字符 S
  • 12 摘自 1-st 和 4第一个字符 S
  • 12 摘自 2-nd 和 3-rd 字符 S
  • 12 摘自 2-nd 和 4第一个字符 S
  • 1122 摘自 1-st 通过 4第一个字符 S

因此,输出 5.

请注意,如果从不同位置提取两个子序列,即使它们与字符串相同,也会单独计数。


示例输入 2

2025

示例输出 2

0

可能不存在 1122 字符串的子序列。


示例输入 3

0777468889971

示例输出 3

30