#include #include #include #include #include #include using namespace std; class RollingHash{ const string& str_; vector c_; vector mod_; vector> hash_; vector> pow_mod_; public: RollingHash(const string& s, const vector& c, const vector& mod) : str_(s), c_(c.begin(), c.end()), mod_(mod.begin(), mod.end()), hash_(mod.size(), vector(s.size()+1, 0)), pow_mod_(mod.size(), vector(s.size()+1, 1)) { assert(c_.size() > 0); assert(c_.size() == mod_.size()); for(int k=0; k get_hash(int l, int r){ vector ret(mod_.size()); int len = r-l; for(int k=0; k> s; int n = s.size(); RollingHash rh(s, {100009ll}, {1ll<<32}); vector dp(n+1, 0); dp[0] = 1; long long ans = 1; for(int i=1; i<=n/2; i++){ for(int j=0; j=mod) dp[i] -= mod; } } ans += dp[i]; if(ans >= mod) ans -= mod; } printf("%lld", ans); return 0; }