var i,n,k:integer;
    a:ansistring;
    palin:array[1..5000,1..5000] of longint;
    f:text;
begin
 assign(f,'progsice.in');
 reset(f);
 readln(f,n);
 readln(f,a);
 close(f);
 for i:=1 to n-1 do
   begin
    palin[i,i]:=1;
    if a[i]=a[i+1] then palin[i,i+1]:=3
                   else palin[i,i+1]:=2;
   end;
 palin[n,n]:=1;
 for k:=1 to n-1 do
   for i:=1 to n-k do
     begin
      if a[i]=a[i+k] then palin[i,i+k]:=palin[i,i+k-1]+palin[i+1,i+k]+1
                     else palin[i,i+k]:=palin[i,i+k-1]+palin[i+1,i+k]-palin[i+1,i+k-1];
      if palin[i,i+k]>1000000007 then palin[i,i+k]:=palin[i,i+k]-1000000007
                                 else if palin[i,i+k]<0 then palin[i,i+k]:=palin[i,i+k]+1000000007;
     end;
 assign(f,'progsice.out');
 rewrite(f);
 writeln(f,palin[1,n]);
 close(f);
end.
