This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
#include <string>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
#include "../str_010_z_algorithm.cpp"
void tiny_test() {
string s; cin >> s;
Z_algorithm<string> za(s);
for(size_t i=0; i<s.length(); i++) {
fprintf(stderr, "Z[%zu] = %d\n", i, za.get_lcp(i));
}
}
void yuki_599() {
const int MOD = 1000000007;
string s; cin >> s; int N = s.size();
vector<int> dp(N + 1);
dp[0] = 1;
for(int i=0; i<N; i++) {
int l = i, r = N - i, len = N - 2*i;
if(len <= 0) continue;
Z_algorithm<string> za(s.substr(l, len));
for(int j=1; j<=len; j++) {
// [ll, lr)
int ll = 0, lr = j;
// [rl, rr)
int rl = len - j, rr = len;
if(lr > rl) break;
if(za.get_lcp(rl) >= j) {
(dp[i+j] += dp[i]) %= MOD;
}
}
}
int ans = 0;
for(int i=0; i<=N; i++) (ans += dp[i]) %= MOD;
cout << ans << endl;
}
int main() {
// tiny_test();
yuki_599();
}
#line 1 "string/verify/verify_str_010_z_algorithm.cpp"
#include <string>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
#line 1 "string/str_010_z_algorithm.cpp"
// Z-algorithm
// 各 Suffix と元の文字列との LCP を求める
template <typename ArrayType>
struct Z_algorithm {
ArrayType v;
vector<int> Z;
void build() {
int N = v.size(), i, j;
Z = vector<int>(N);
for(i=1,j=0; i<N; i++) {
int l = i - j;
if(i + Z[l] < j + Z[j]) {
Z[i] = Z[l];
}
else {
int k = max(0, j + Z[j] - i);
while(i + k < N and v[k] == v[i+k]) k++;
Z[i] = k;
j = i;
}
}
Z[0] = N;
}
Z_algorithm(ArrayType v_) : v(v_) {
build();
}
// idx から切り出した Suffix と文字列全体との LCP
int get_lcp(int idx) {
return Z[idx];
}
};
#line 7 "string/verify/verify_str_010_z_algorithm.cpp"
void tiny_test() {
string s; cin >> s;
Z_algorithm<string> za(s);
for(size_t i=0; i<s.length(); i++) {
fprintf(stderr, "Z[%zu] = %d\n", i, za.get_lcp(i));
}
}
void yuki_599() {
const int MOD = 1000000007;
string s; cin >> s; int N = s.size();
vector<int> dp(N + 1);
dp[0] = 1;
for(int i=0; i<N; i++) {
int l = i, r = N - i, len = N - 2*i;
if(len <= 0) continue;
Z_algorithm<string> za(s.substr(l, len));
for(int j=1; j<=len; j++) {
// [ll, lr)
int ll = 0, lr = j;
// [rl, rr)
int rl = len - j, rr = len;
if(lr > rl) break;
if(za.get_lcp(rl) >= j) {
(dp[i+j] += dp[i]) %= MOD;
}
}
}
int ans = 0;
for(int i=0; i<=N; i++) (ans += dp[i]) %= MOD;
cout << ans << endl;
}
int main() {
// tiny_test();
yuki_599();
}