Symmetric Scenic Subsequence

VFleaKing loves to enjoy the scenic views along a mountain road. The road is represented by a string s consisting only of the characters a and b. The characters stand for whether a 10‐cm segment of the road offers a beautiful view (a) or not (b). When going uphill, the road is traversed in the order of the string. When going downhill the road is the reverse of that string.

VFleaKing will choose a subsequence of segments (by selecting some indices x₁,x₂, …, x_k with k > 0 and 1 ≤ x1 < x2 < … < xk ≤ n) at which he looks at the view. On the way up he sees the view at positions s[x1], s[x2], …, s[xk] (we denote this sequence by T1) and on the way down he sees the view at positions s[xk], s[xk-1], …, s[x1] (denoted by T2). He wishes that the scenic conditions are identical, namely T1 = T2.

In addition, he wants the time intervals between his viewings to be equal on the uphill and downhill journeys. If we let P1 = [x2 - x1, x3 - x2, …, xk - xk-1] and P2 = [xk - xk-1, xk-1 - xk-2, …, x2 - x1], he requires P1 = P2.

In other words, the chosen subsequence must be symmetric in two senses:

• The view sequence is a palindrome: s[x1], s[x2], …, s[xk] must equal its reverse.
• The gaps between indices, namely x2-x1, x3-x2, …, xk-xk-1, form a palindromic sequence as well.

Finally, VFleaKing fears that if during the time from his first to his last look he never lowers his head (i.e. if the chosen segments form a contiguous block in s), he will fall. More precisely, if xi = x1 + i - 1 for all i, then the selection is forbidden.

---

This means that you are to count the number of subsequences of positions (with at least 2 elements) in the given string s that satisfy:

1. The indices x₁, x₂, …, x_k and their corresponding characters are symmetric about some axis. In other words, if C = x1 + xk, then for all i, xi + xk+1-i = C and s[xi] = s[xk+1-i] (where indices are 1-indexed).
2. The chosen indices x do not form a contiguous segment of s; that is, it is not the case that xi = x1 + i - 1 for all i.

One can show that every such symmetric subsequence has its two ends i and j (with 1 ≤ i < j ≤ n, and s[i] = s[j]) and all the other chosen positions lie between them in mirror pairs. For fixed endpoints i and j (with j - i ≥ 2) the positions between them form an interval of length m = j - i - 1. A symmetric selection from this interval is determined by choosing a set that is invariant under reflection about the center of the interval. It can be shown that the number of ways to choose such a set (possibly empty) is given by:

• If m is odd: the number is 2^((m+1)/2) (each choice for the middle pair) and then subtract 1 to remove the case that yields a contiguous block.
• If m is even: the number is 2^(m/2) and subtract 1.

More precisely, for each pair of indices i < j with s[i] = s[j] and j - i ≥ 2, let m = j - i - 1. Define

$$G(m)=\begin{cases} 2^{\frac{m+1}{2}}-1,&\text{if }m\text{ is odd},\\[1mm] 2^{\frac{m}{2}}-1,&\text{if }m\text{ is even}. \end{cases} $$

Your task is to output the total number of legal symmetric subsequences modulo 109+7.

inputFormat

The input consists of a single line containing a nonempty string s consisting only of characters a and b.

outputFormat

Output a single integer: the number of legal symmetric subsequences (with at least two positions and not forming a contiguous block) modulo 109+7.

sample

aba

1