BZOJ3160万径人踪灭

uses math;
const
  mo=1000000007;
type
  xs=record
    x,y:double;
  end;
  arr=array[0..270001]of xs;
var
  e,t:arr;
  a:array[1..5]of arr;
  n,m,i,ll,ans:longint;
  ch:array[-2..270001]of char;
  b:array[-2..270001]of longint;
  z,ksm:array[0..270001]of longint;
  s:ansistring;
operator -(a,b:xs)c:xs;
begin c.x:=a.x-b.x; c.y:=a.y-b.y; end;
operator +(a,b:xs)c:xs;
begin c.x:=a.x+b.x; c.y:=a.y+b.y; end;
operator *(a,b:xs)c:xs;
begin c.x:=a.x*b.x-a.y*b.y; c.y:=a.x*b.y+a.y*b.x; end;
procedure manacher;
var k,l,i:longint;
begin
  k:=-1; l:=-1; b[-1]:=1;
  for i:=0 to m*2-1 do
  begin
    if l>=i then
    b[i]:=min(b[2*k-i],l-i+1)else b[i]:=1;
    while true do
    begin
      if ch[i+b[i]]=ch[i-b[i]] then inc(b[i])
      else break;
    end;
    ans:=(ans+mo-(b[i]shr 1))mod mo;
    if i+b[i]-1>l then begin l:=i+b[i]-1; k:=i; end;
  end;
end;
procedure fft(xx:longint);
var i,j,q,k,l,c:longint;
  t:xs;
begin
  for i:=0 to n-1 do a[xx+2,z[i]]:=a[xx,i];
  xx:=xx+2;
  k:=n; l:=1;
  for i:=ll downto 1 do
  begin
    k:=k shr 1;
    for j:=0 to k-1 do
    begin
      c:=j*2*l;
      for q:=0 to l-1 do
      begin
        t:=e[q*k]*a[xx,c+l];
        a[xx,c+l]:=a[xx,c]-t;
        a[xx,c]:=a[xx,c]+t;
        inc(c);
      end;
    end;
    l:=l*2;
  end;
end;
begin
  readln(s); m:=length(s);
  ch[-2]:=‘+‘;
  for i:=0 to m-1 do ch[i*2]:=s[i+1];
  ch[m*2+1]:=‘-‘;
  manacher;
  for i:=0 to m-1 do if ch[i*2]=‘a‘ then a[1,i].x:=1;
  for i:=0 to m-1 do if ch[i*2]=‘b‘ then a[2,i].x:=1;
  n:=1;
  while n<m*2 do begin n:=n*2; inc(ll); end;
  for i:=1 to n-1 do z[i]:=(z[i shr 1]shr 1)or((i and 1)shl(ll-1));
  ksm[0]:=1; for i:=1 to 100000 do ksm[i]:=(ksm[i-1]*2)mod mo;
  for i:=0 to n-1 do e[i].x:=cos(pi*2*i/n);
  for i:=0 to n-1 do e[i].y:=sin(pi*2*i/n);
  fft(1); fft(2);
  for i:=0 to n-1 do a[3,i]:=a[3,i]*a[3,i]+a[4,i]*a[4,i];
  for i:=0 to n-1 do e[i].y:=-e[i].y;
  fft(3);
  for i:=0 to m-1 do a[5,i*2].x:=a[5,i*2].x+n;
  for i:=0 to n-1 do ans:=(ans+ksm[round(a[5,i].x/2/n)]-1)mod mo;
  writeln(ans);
end.