Program Subpalindromes;
Const MaxLen=10000;
      Base = 29876543;
Type TTableRow = Array [1..MaxLen] of LongInt;

Var f: Text;
    s: Array [1..MaxLen] of Char;
    len: Word;  // input length
    delta: Word; // R-L
    r0, r1, r2: TTableRow;
    i: Word;
Begin
//  Assign(f, 'palin.in'); Reset(f);
  len:= 0;
  Repeat
    Inc(len);
    Read(s[len]);
  Until SeekEoF;
//  Close(f);

  For i:= 1 To len Do Begin
    r0[i]:= 0;
    r1[i]:= 1;
  End;
  For delta:= 1 To len-1 Do Begin
    For i:= 1 To len-delta Do Begin
      If s[i]=s[i+delta] Then Begin
        r2[i]:= (r1[i+1]+r1[i]+1) mod Base;
      End
      Else Begin
        r2[i]:= (r1[i+1]+(Base-r0[i+1])+r1[i]) mod Base;
      End;
    End;
    For i:= 1 To len Do Begin
      r0[i]:= r1[i];
      r1[i]:= r2[i];
    End;
  End;

//  Assign(f, 'palin.out'); Rewrite(f);
  Writeln(r1[1]);
//  Close(f);
End.

