F - 1122 Subsequence 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

数字からなる文字列 S が与えられます。

以下の条件を全て満たす文字列 T を 1122文字列 と呼びます。（定義は C 問題と同じです。）

  • T は数字からなる空でない文字列
  • |T| は偶数。ここで、 |T| は文字列 T の長さを表す
  • T の 1 文字目から \frac{|T|}2 文字目までは全て同じ数字である
  • T の \frac{|T|}2+1 文字目から |T| 文字目までは全て同じ数字である
  • T の 1 文字目の数字に 1 を足すと |T| 文字目の数字になる

例えば 1122 や 01 、 444555 などは 1122文字列 ですが、 1222 や 90 は 1122文字列 ではありません。

S の （連続でなくても良い）部分列 であって 1122文字列 であるものの個数を 998244353 で割ったあまりを求めてください。

ただし、ある二つの部分列が文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えるものとします。

制約

  • S は長さ 1 以上 10^6 以下の数字からなる文字列

入力

入力は以下の形式で標準入力から与えられる。

S

出力

S の部分列であって 1122文字列 であるものの個数を 998244353 で割ったあまりを出力せよ。

入力例 1

1122

出力例 1

5

以下の 5 つの部分列が条件を満たします。

  • S の 1 文字目と 3 文字目を取り出した 12
  • S の 1 文字目と 4 文字目を取り出した 12
  • S の 2 文字目と 3 文字目を取り出した 12
  • S の 2 文字目と 4 文字目を取り出した 12
  • S の 1 文字目から 4 文字目を取り出した 1122

したがって、 5 を出力してください。

文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えることに注意してください。

入力例 2

2025

出力例 2

0

1122文字列 となる部分列が存在しない場合もあります。

入力例 3

0777468889971

出力例 3

30

Score : 500 points

Problem Statement

You are given a string S consisting of digits.

A string T is called a 1122-string if it satisfies all of the following conditions. (The definition is the same as in Problem C.)

  • T is a non-empty string consisting of digits.
  • |T| is even, where |T| denotes the length of string T.
  • All characters from the 1-st through the \frac{|T|}2-th character of T are the same digit.
  • All characters from the (\frac{|T|}2+1)-th through the |T|-th character of T are the same digit.
  • Adding 1 to the digit of the 1-st character of T gives the digit of the |T|-th character.

For example, 1122, 01, and 444555 are 1122-strings, but 1222 and 90 are not 1122-strings.

Find the number, modulo 998244353, of (not necessarily contiguous) subsequences of S that are 1122-strings.

Two subsequences are counted separately if they are extracted from different positions, even if they are identical as strings.

Constraints

  • S is a string consisting of digits with length between 1 and 10^6, inclusive.

Input

The input is given from Standard Input in the following format:

S

Output

Output the number, modulo 998244353, of subsequences of S that are 1122-strings.

Sample Input 1

1122

Sample Output 1

5

The following five subsequences satisfy the condition.

  • 12 extracted from the 1-st and 3-rd characters of S
  • 12 extracted from the 1-st and 4-th characters of S
  • 12 extracted from the 2-nd and 3-rd characters of S
  • 12 extracted from the 2-nd and 4-th characters of S
  • 1122 extracted from the 1-st through 4-th characters of S

Thus, output 5.

Note that two subsequences are counted separately if they are extracted from different positions, even if they are identical as strings.

Sample Input 2

2025

Sample Output 2

0

There may be no subsequence that is a 1122-string.

Sample Input 3

0777468889971

Sample Output 3

30