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