import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; const long MOD = 10^^9 + 7; const long BASE = 97; void main() { auto S = readln.chomp; auto N = S.length.to!int; auto powmod = new long[](N+1); powmod[0] = 1; foreach (i; 0..N) powmod[i+1] = powmod[i] * BASE % MOD; auto table = new long[][](N+1, N+1); foreach (i; 0..N+1) table[i].fill(-1); foreach (k; 1..N+1) { long hash = 0; foreach (i; 0..k) { hash = hash * BASE % MOD; hash = (hash + S[i]-'a') % MOD; } table[k][0] = hash; foreach (i; 1..N-k+1) { hash = hash - (S[i-1] - 'a') * powmod[k-1] % MOD; hash = hash * BASE % MOD; hash = (hash + S[i+k-1]-'a') % MOD; hash = (hash + MOD) % MOD; table[k][i] = hash; } } auto mem = new long[](N); mem.fill(-1); long dfs(int l) { if (l >= N/2) return 0; if (mem[l] >= 0) return mem[l]; int r = N - l - 1; long ret = 0; foreach (len; 1..N) { if (l+len-1 >= N/2) break; if (table[len][l] == table[len][r-len+1]) (ret += dfs(l+len) + 1) %= MOD; } mem[l] = ret; return ret; } writeln(dfs(0)+1); }