#include #include #include const long long int MOD=1e9+7; const long long int BASE=31; using namespace std; vector memo; struct RollingHush { vector hash; vector power; string str; RollingHush(string s) : hash(s.size()+1), power(s.size()+1) { str=s; hash[0]=0; power[0]=1; for(int si=0; si0 && mid<=rh.size()/2 && rh.size()/2<=right+left-mid) { if(rh.size()/2-mid<=cur) { count += memo[cur-1]; } else { memo.push_back(count_kaibunkai(rh, mid, right+left-mid, cur+1)); count += memo[cur]; } mid--; continue; } count += count_kaibunkai(rh, mid, right+left-mid, cur+1); } mid--; } return count; } int main() { string str; cin >> str; RollingHush rh_str(str); memo.push_back(1); cout << count_kaibunkai(rh_str, 0, str.size(), 0) << endl; return 0; }