Empty String

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4constexpr int M=1e9+7;
5
6inline int add(int a,int b){
7  a+=b;
8  if(a>=M) a-=M;
9  return a;
10}
11
12inline int mul(int a,int b){
13  return a*b%M;
14}
15
16int binpow(int a,int b){
17  int res=1;
18  while(b){
19    if(b&1) res=mul(res,a);
20    a=mul(a,a),b>>=1;
21  }
22  return res;
23}
24signed main(){
25  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
26  string s; cin>>s;
27  int n=s.size();
28  if(n&1){
29    cout<<"0\n";
30    return 0;
31  }
32
33  int f[n/2+1]; f[0]=1;
34  for(int i=1;i<=n/2;++i) f[i]=mul(f[i-1],i);
35  int invf[n/2+1]; invf[0]=1;
36  for(int i=1;i<=n/2;++i) invf[i]=binpow(f[i],M-2);
37  auto C=[&](const int&N,const int&K){
38    return mul(f[N],mul(invf[K],invf[N-K]));
39  };
40
41  int dp[n][n]{};
42  for(int i=0;i<n-1;++i) if(s[i]==s[i+1]){
43    dp[i][i+1]=1;
44  }
45  for(int l=4;l<=n;l+=2){
46    for(int i=0;i<=n-l;++i){
47      int j=i+l-1;
48      for(int k=i+1;k<=j;k+=2) if(s[i]==s[k]){
49        dp[i][j]=add(dp[i][j],
50            mul((i+1<k?dp[i+1][k-1]:1),
51            mul((k<j?dp[k+1][j]:1),
52            C(l/2,(j-k)/2))));
53      }
54    }
55  }
56  //for(int i=0;i<n;++i){ for(int j=0;j<n;++j) cout<<dp[i][j]<<" "; cout<<'\n'; }
57  cout<<dp[0][n-1]<<'\n';
58  return 0;
59}