E - ABBreviate Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1300 点

問題文

a と b のみからなる文字列 s があります。 すぬけ君は、次の 2 種類の操作を任意の順序で任意の回数だけ行えます。

  • s 中の部分文字列 aa を一箇所選び、b へ置き換える。
  • s 中の部分文字列 bb を一箇所選び、a へ置き換える。

0 回以上の操作の後、s は何通りありうるでしょうか？ 10^9 + 7 で割った余りを求めてください。

制約

  • 1 \leq |s| \leq 10^5
  • s は a と b のみからなる。

入力

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

s

出力

操作後の s は何通りありうるか？ 10^9 + 7 で割った余りを出力せよ。

入力例 1

aaaa

出力例 1

6

次の 6 通りです。

  • aaaa
  • aab
  • aba
  • baa
  • bb
  • a

入力例 2

aabb

出力例 2

5

次の 5 通りです。

  • aabb
  • aaa
  • bbb
  • ab
  • ba

入力例 3

ababababa

出力例 3

1

すぬけ君は一度も操作を行えません。

入力例 4

babbabaaba

出力例 4

35

Score : 1300 points

Problem Statement

There is a string s consisting of a and b. Snuke can perform the following two kinds of operation any number of times in any order:

  • Choose an occurrence of aa as a substring, and replace it with b.
  • Choose an occurrence of bb as a substring, and replace it with a.

How many strings s can be obtained by this sequence of operations? Find the count modulo 10^9 + 7.

Constraints

  • 1 \leq |s| \leq 10^5
  • s consists of a and b.

Input

Input is given from Standard Input in the following format:

s

Output

Print the number of strings s that can be obtained, modulo 10^9 + 7.

Sample Input 1

aaaa

Sample Output 1

6

Six strings can be obtained:

  • aaaa
  • aab
  • aba
  • baa
  • bb
  • a

Sample Input 2

aabb

Sample Output 2

5

Five strings can be obtained:

  • aabb
  • aaa
  • bbb
  • ab
  • ba

Sample Input 3

ababababa

Sample Output 3

1

Snuke cannot perform any operation.

Sample Input 4

babbabaaba

Sample Output 4

35