Problem Background

Mr. Bao is a good driver who always takes students up the mountain for fun. However, after his last trip last year due to some strange reasons, he changed careers. For half a year, no one has traveled up this road again.

When VFleaKing returned to this mountain, he found that the bustling tourists of the past were gone. Back when Mr. Bao was still around, not all the people coming to the mountain were there to appreciate the scenery.

Problem Description

If the computer room is about to close, or you need to leave urgently, please skip directly to the sixth paragraph.

VFleaKing noticed this dirt road up and down the mountain, where some sections offer beautiful views, while others do not. Dividing the road into segments every 10 cm, for each segment, using a to denote a beautiful view and b to denote no beautiful view, we get a string $s$ consisting only of a and b. Since the road down is the same as the road up but in reverse, the string for the downhill path is the reverse of the uphill path.

Let the uphill string length be $n$, with characters $s_1, s_2, \ldots, s_n$. On the uphill and downhill paths, VFleaKing will choose certain segments to look at the scenery, while walking with his head down at other times. That is, VFleaKing will choose $k$ segments $x_1, x_2, \ldots, x_k$, with $k > 0$ and $1 \le x_1 < x_2 < \ldots < x_k \le n$, where VFleaKing will look at the scenery during these segments on both the uphill and downhill paths.

VFleaKing hopes that the scenery seen on the uphill and downhill paths is the same. That is, the sequence of whether he saw beautiful views on the uphill path is $s_{x_1}, s_{x_2}, \ldots, s_{x_k}$, denoted as sequence $T_1$, and on the downhill path is $s_{x_k}, s_{x_{k-1}}, \ldots, s_{x_1}$, denoted as sequence $T_2$. VFleaKing wants $T_1 = T_2$.

VFleaKing also hopes that the intervals between viewing the scenery are the same on both paths. That is, the intervals on the uphill path are $x_2 - x_1, x_3 - x_2, \ldots, x_k - x_{k-1}$, denoted as sequence $P_1$. On the downhill path, the intervals are $x_k - x_{k-1}, x_{k-1} - x_{k-2}, \ldots, x_2 - x_1$, denoted as sequence $P_2$. VFleaKing wants $P_1 = P_2$.

VFleaKing thinks that if he never looks down during the time from the first to the last viewing, he will fall. That is, if for all $1 \le i \le k$, $x_i = x_1 + i - 1$, VFleaKing will fall, and he does not want this to happen.

The task is to select a subsequence from a string consisting only of a and b, such that:

1. The positions and characters are symmetric about a certain axis.
2. It cannot be a continuous segment.

For example, given $s = \texttt{"abaaaaabbabbabaa"}$, sequences like $[1, 4]$, $[5, 8, 10, 12, 15]$, and $[4, 5, 8, 9, 10, 11, 12, 15, 16]$ are valid. However, $[1, 2]$ does not meet VFleaKing's first and third wishes, so it is not valid. $[1, 2, 4]$ does not meet the second wish, so it is not valid. $[9, 10, 11]$ does not meet the third wish, so it is not valid.

Given the string $s$, VFleaKing wants to know how many valid sequences $x$ exist. The answer may be very large, so VFleaKing wants the result modulo $1000000007$.

Input Format

A single line containing a string consisting only of the characters a and b.

Output Format

A single line containing a non-negative integer representing the answer to the problem.

Sample Input and Output

Input Sample #1

abaabaa

Output Sample #1

14

Input Sample #2

aaabbbaaa

Output Sample #2

44

Input Sample #3

aaaaaaaa

Output Sample #3

53

Notes

Sample Explanation 1

The 14 valid sequences are:

• $[1, 3]$, $[1, 4]$, $[2, 5]$, $[1, 6]$, $[3, 6]$, $[4, 6]$, $[1, 7]$, $[3, 7]$, $[4, 7]$;
• $[1, 4, 7]$, $[3, 5, 7]$;
• $[1, 3, 4, 6]$, $[1, 2, 5, 6]$, $[3, 4, 6, 7]$.

Sample Explanation 2

I have thought of a wonderful explanation, but there are too many solutions to write down.

Sample Explanation 3

I have thought of a wonderful explanation, but there are too many solutions to write down.

Data Range

• $10\%$ of the data, the string contains only the letter a or the letter b.
• Another $20\%$ of the data, $n \le 1000$.
• Another $20\%$ of the data, the number of as is no more than 10, or the number of bs is no more than 10.
• Another $10\%$ of the data, $n \le 10000$.
• For $100\%$ of the data, $n \le 100000$.

Source

• 2013 Hubei Inter-School Test week1
• bzoj 3160
• Information Science Olympiad Mathematics Comprehensive
• stong9070整理

见题面 Input 部分

见题面 Output 部分