Problem Statement

Given is a string S. From this string, Takahashi will make a new string T as follows.

• First, mark one or more characters in S. Here, no two marked characters should be adjacent.
• Next, delete all unmarked characters.
• Finally, let T be the remaining string. Here, it is forbidden to change the order of the characters.

How many strings are there that can be obtained as T? Find the count modulo (10^9 + 7).

Input

Input is given from Standard Input in the following format:
S

Output

Print the number of different strings that can be obtained as T, modulo (10^9 + 7).

Constraints

• S is a string of length between 1 and $2 \times 10^5$ (inclusive) consisting of lowercase English letters.

Sample Input 1

abc

Sample Output 1

4

There are four strings that can be obtained as T: a, b, c, and ac.
Marking the first character of S yields a;
marking the second character of S yields b;
marking the third character of S yields c;
marking the first and third characters of S yields ac.
Note that it is forbidden to, for example, mark both the first and second characters.

Sample Input 2

aa

Sample Output 2

1

There is just one string that can be obtained as T, which is a.
Note that marking different positions may result in the same string.

Sample Input 3

acba

Sample Output 3

6

There are six strings that can be obtained as T: a, b, c, aa, ab, and ca.

Sample Input 4

chokudai

Sample Output 4

54

见题面 Input 部分

见题面 Output 部分