#include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair PII; typedef vector VI; typedef vector VVI; #define MP make_pair #define PB push_back #define inf 1000000007 ll mod = inf; bool ok[6000][6000]; ll dp[5010]; int main(){ string s; cin >> s; int n = (int)s.size(); if(n%2==0){ s.insert(s.begin()+n/2,'-'); n++; } int m = (n-1)/2; for(int i=0;im)break; if(i==0){ if(s[j]==s[n-1-j]){ ok[j][j] = 1; } }else{ bool flag = 1; for(int k=0;k<=i;k++){ if(s[j+k]!=s[n-j-1-i+k]){ flag = 0; break; } } if(flag){ ok[j][j+i] = 1; } } } } dp[m] = 1; for(int i=m-1;i>=0;i--){ dp[i] = 1; for(int j=i;j<=m-1;j++){ if(ok[i][j]==1){ dp[i] = (dp[i]+dp[j+1])%mod; } } } cout << dp[0] << endl; return 0; }