1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int INF = 1<<30;
typedef long long LL;
const LL mod = 1000000007;
const double pi = acos(-1);
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
const int MAXN = 100005;

struct Complex{
	double x, y;
	Complex() { x=y=0; }
	Complex(double tx, double ty) { x = tx; y = ty; }
	Complex operator + (Complex a) { return Complex(x+a.x, y+a.y); }
	Complex operator - (Complex a) { return Complex(x-a.x, y-a.y); }
	Complex operator * (Complex a) { return Complex(x*a.x-y*a.y, y*a.x+x*a.y); }
}A[MAXN<<2], B[MAXN<<2], C1[MAXN<<2], C2[MAXN<<2];
LL C3[MAXN<<2];
char str[MAXN], tmp[MAXN<<1];
int len, rad[MAXN<<1], R[MAXN<<2], n;
LL ksm(LL a, LL b) {
	LL tmp = a, ret = 1;
	while (b) {
		if (b & 1) ret = (ret * tmp) % mod;
		tmp = (tmp * tmp) % mod;
		b >>= 1;
	}
	return ret;
}
void FFT(Complex *a, double f) {
	for (int i = 1; i < n; ++i) if (i < R[i]) swap(a[i], a[R[i]]);
	for (int i = 1; i < n; i <<= 1) {
		Complex wn(cos(pi / i), f * sin(pi / i));
		for (int j = 0; j < n; j += (i << 1)) {
			Complex w(1, 0);
			for (int k = 0; k < i; ++k) {
				Complex x = a[j+k], y = a[j+k+i] * w;
				a[j+k] = x+y;
				a[j+k+i] = x-y;
				w = w * wn;
			}
		}
	}
	if (f == -1) for (int i = 0; i < n; ++i) a[i].x /= n;
}
int main() {
	scanf("%s", str);
	len = strlen(str);
	tmp[0] = '#'; tmp[1] = '$'; int ptr = 1;
	for (int i = 0; i < len; ++i) {
		tmp[++ptr] = str[i];
		tmp[++ptr] = '$';
	}
	int upper = 1; rad[1] = 1; int mxid = 1;
	for (int i = 2; i <= ptr; ++i) {
		if (upper >= i) rad[i] = min(upper - i + 1, rad[mxid*2-i]);
		else rad[i] = 1;
		while (tmp[i+rad[i]] == tmp[i-rad[i]]) ++rad[i];
		if (i+rad[i]-1 > upper) {
			upper = i+rad[i] - 1;
			mxid = i;
		}
	}
	LL ans = 0;
	for (int i = 1; i <= ptr; ++ i) ans -= (rad[i] / 2);
	int mx = len*2-1, L=0;
	for (n = 1; n <= mx; n<<=1) ++L;
	for (int i = 1; i < n; ++i) R[i] = (R[i>>1]>>1)|((i&1) << L-1);
	for (int i = 0; i < n; ++i) A[i].x = A[i].y = B[i].x = B[i].y = 0;
	for (int i = 0; i < len; ++i) {
		if (str[i]=='a') A[i].x = 1;
		else A[i].x = 0;
		B[i].x = A[i].x;
		A[i].y = B[i].y = 0;
	}
	FFT(A, 1); FFT(B, 1);
	for (int i = 0; i < n; ++i) C1[i] = A[i] * B[i];
	FFT(C1, -1);
	for (int i = 0; i < n; ++i) A[i].x = A[i].y = B[i].x = B[i].y = 0;
	for (int i = 0; i < len; ++i) {
		if (str[i]=='b') A[i].x = 1;
		else A[i].x = 0;
		B[i].x = A[i].x;
		A[i].y = B[i].y = 0;
	}
	FFT(A, 1); FFT(B, 1);
	for (int i = 0; i < n; ++i) C2[i] = A[i] * B[i];
	FFT(C2, -1);
	for (int i = 0; i < n; ++i) C3[i] = LL(C1[i].x+0.5) + LL(C2[i].x+0.5);
	upper = 2*len-1;
	for (int i = 0; i < upper; ++i) ans += (ksm(2, (C3[i]+1)/2) - 1);
	printf("%lld", ans % mod);
}