uses math;
const
        maxN    =5*trunc(1e4)+1;
        base    =trunc(1e9) + 7;
type
        ansi    = AnsiString;
var
        ff, gg: text;   i: longint;
        S: ansi;
        n: longint;
 
        pow: array[0..maxN] of int64;
        hash: array[0..maxN] of int64;
 
function getHash(i, j: longint): int64;
  begin
        getD:= (hash[j]-hash[i-1]*pow[j-i+1] + base*base) mod base;
  end;
 
begin
		// n = length(S);
        pow[0]:= 1;
        for i:= 1 to N do pow[i]:=(pow[i-1]*26) mod base;
 
        for i:= 1 to N do     hash[i]:= (hash[i-1]*26 + ord(S[i]) - ord('a'))mod base;
end.
 
 

dXNlcyBtYXRoOwpjb25zdAogICAgICAgIG1heE4gICAgPTUqdHJ1bmMoMWU0KSsxOwogICAgICAgIGJhc2UgICAgPXRydW5jKDFlOSkgKyA3Owp0eXBlCiAgICAgICAgYW5zaSAgICA9IEFuc2lTdHJpbmc7CnZhcgogICAgICAgIGZmLCBnZzogdGV4dDsgICBpOiBsb25naW50OwogICAgICAgIFM6IGFuc2k7CiAgICAgICAgbjogbG9uZ2ludDsKCiAgICAgICAgcG93OiBhcnJheVswLi5tYXhOXSBvZiBpbnQ2NDsKICAgICAgICBoYXNoOiBhcnJheVswLi5tYXhOXSBvZiBpbnQ2NDsKCmZ1bmN0aW9uIGdldEhhc2goaSwgajogbG9uZ2ludCk6IGludDY0OwogIGJlZ2luCiAgICAgICAgZ2V0RDo9IChoYXNoW2pdLWhhc2hbaS0xXSpwb3dbai1pKzFdICsgYmFzZSpiYXNlKSBtb2QgYmFzZTsKICBlbmQ7CgpiZWdpbgoJCS8vIG4gPSBsZW5ndGgoUyk7CiAgICAgICAgcG93WzBdOj0gMTsKICAgICAgICBmb3IgaTo9IDEgdG8gTiBkbyBwb3dbaV06PShwb3dbaS0xXSoyNikgbW9kIGJhc2U7CgogICAgICAgIGZvciBpOj0gMSB0byBOIGRvICAgICBoYXNoW2ldOj0gKGhhc2hbaS0xXSoyNiArIG9yZChTW2ldKSAtIG9yZCgnYScpKW1vZCBiYXNlOwplbmQuCgo=