#include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long int MOD = 1000000007; signed main() { cin.tie(0); ios::sync_with_stdio(false); string S; cin >> S; //S.clear(); int N = S.size(); vector A(N); int res = 0; vector dp((N / 2) + 2, 0); dp[0] = 1; int nn = N; for (int x = 0; x < nn / 2; x++) { N = S.size(); A[x] = S.size(); int i = 1, j = 0; for (int i = 0; i < N; i++) { A[i] = 0; } while (i < S.size()) { while (i + j < S.size() && S[j] == S[i + j]) ++j; A[i] = j; if (j == 0) { ++i; continue; } int k = 1; while (i + k < S.size() && k + A[k] < j) A[i + k] = A[k], ++k; i += k; j -= k; } S.pop_back(); S.erase(S.begin()); for (int k = ((N - 1) / 2) + 1; k < N; k++) { if (A[k] == N - k) { //cerr << x << " " << x + N - k << endl; dp[x + N - k] = (dp[x + N - k] + dp[x]) % MOD; } } //cerr << dp[x] << endl; //res = (res + dp[x]) % MOD; } for (int i = 0; i < dp.size(); i++) { //cerr << dp[i] << " "; res = (res + dp[i]) % MOD; } //cerr << endl; cout << res << endl; }