#include using namespace std; typedef long long ll; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b Manacher(string S){ vector R(si(S)); int i = 0, j = 0; while (i < S.size()) { while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j; R[i] = j; int k = 1; while (i-k >= 0 && k+R[i-k] < j) R[i+k] = R[i-k], ++k; i += k; j -= k; } return R; } // 偶数長のも求めるために$を入れる必要がある //ロリハ struct Rollinghash{ string S; int n; int base1; int base2; vector h1,h2,ru1,ru2; void make(string &T,int ba1,int ba2){ S=T; n=S.size(); h1.assign(n+1,0); h2.assign(n+1,0); ru1.assign(n+1,0); ru2.assign(n+1,0); base1=ba1; base2=ba2; ru1[0]=1; ru2[0]=1; for(int i=1;i<=n;i++){ h1[i]=h1[i-1]*base1+ll(S[i-1]-'$'+1); h1[i]%=mod1; h2[i]=h2[i-1]*base2+ll(S[i-1]-'$'+1); h2[i]%=mod2; ru1[i]=ru1[i-1]*base1%mod1; ru2[i]=ru2[i-1]*base2%mod2; } } pair ha(int l,int r){ pair res; res.fi=(h1[r]-h1[l]*ru1[r-l]%mod1+mod1)%mod1; res.se=(h2[r]-h2[l]*ru2[r-l]%mod2+mod2)%mod2; return res; }//開区間 }; //強連結成分分解 int V,cmp[MAX]; vector G[MAX],rG[MAX],vs;//vsがトポソの逆順になってる bool used[MAX]; int get_id(int i,bool f){ return 2*i+f; } void add_edge(int from,int to){ G[from].push_back(to); rG[to].push_back(from); } void either(int i,bool f,int j,bool g){ add_edge(get_id(i,!f),get_id(j,g)); add_edge(get_id(j,!g),get_id(i,f)); //add_edge(2*i+(!f),2*j+g); //add_edge(2*j+(!g),2*i+f); } void imply(int i,bool f,int j,bool g){ either(i,!f,j,g); } //iがfならばjがg void must(int i,bool f){ either(i,f,i,f); } void DFS(int v){ used[v]=1; for(int i=0;i=0;i--){ if(used[vs[i]]==0) rDFS(vs[i],k++); } return k; } ll dp[MAX]; void init(int sz){ V=sz; for(int i=0;i>S>>T; string SS,TT; SS+='$';TT+='$'; for(char c:S){ SS+=c; SS+='$'; } for(char c:T){ TT+=c; TT+='$'; } S=SS; T=TT; ll ha1=103,ha2=109; map,ll> MA1,MA2; for(int q=0;q<2;q++){ map,ll> dic; Rollinghash ro; ro.make(S,ha1,ha2); init(MAX); auto mana=Manacher(S); for(int i=0;i la=mp(-1,-1); for(int l=s;l<=i;l+=2){ int r=i+(i-l)+1; auto re=ro.ha(l,r); if(dic.count(re)){ if(l==s) dp[dic[re]]++; else{ add_edge(dic[la],dic[re]); } break; }else{ int sz=si(dic); dic[re]=sz; if(l==s) dp[sz]++; else{ add_edge(dic[la],dic[re]); } la=re; } } } V=si(dic); scc(); reverse(all(vs)); for(int a:vs){ for(int to:G[a]){ dp[to]+=dp[a]; } } for(auto a:dic){ MA1[a.fi]+=dp[a.se]; } swap(S,T); swap(MA1,MA2); } ll ans=0; for(auto a:MA1){ if(MA2.count(a.fi)) ans+=a.se*MA2[a.fi]; } cout<