#include<deque> #include<queue> #include<vector> #include<algorithm> #include<iostream> #include<set> #include<cmath> #include<tuple> #include<string> #include<chrono> #include<functional> #include<iterator> #include<random> #include<unordered_set> #include<unordered_map> #include<array> #include<map> #include<bitset> #include<iomanip> using namespace std; typedef long long int llint; typedef long double lldo; #define mp make_pair #define mt make_tuple #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define fir first #define sec second #define res resize #define ins insert #define era erase #define dme cout<<"IMPOSSIBLE"<<endl;return 0 //ios::sync_with_stdio(false); //std::cin.tie(0); //<< setprecision(20) const int mod=1e9+7;//19234567892927; const llint mmd=1e9+7; const int big=1e12+100; const long double pai=3.141592653589793238462643383279502884197; const long double ena=2.71828182845904523536; const long double eps=1e-7; template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}} template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}} llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);} llint lcm(llint a,llint b){return a/gcd(a,b)*b;} int main(void){ string str;cin>>str; int n=str.size(),i,j; //roaring hash!!!!!!!!!!!! //回転微塵斬!!!!!!!!!!!!! vector<llint>haa(n+1); llint gen=1;haa[0]=1; llint hos[5005]={0};hos[0]=1; for(i=1;i<5005;i++){hos[i]=hos[i-1]*29%mmd;} for(i=0;i<n;i++){gen*=29;gen+=str[i];gen%=mmd;haa[i+1]=gen;} static bool dp[5001][5001]={0}; for(i=0;i<=n/2;i++){ for(j=i+1;j<=n/2;j++){ llint mae=(mmd+(haa[i]*hos[j-i])-haa[j])%mmd; llint ato=(mmd+(haa[n-j]*hos[j-i])-haa[n-i])%mmd; if(mae==ato){dp[i][j]=true;} } } llint ans=1; static llint ddp[5005]={0};ddp[0]=1; for(i=1;i<=n/2;i++){ for(j=0;j<i;j++){ if(dp[j][i]){ddp[i]+=ddp[j];} } ddp[i]%=mod;ans+=ddp[i];ans%=mod; } cout<<ans<<endl; return 0; }