#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; vector< int > manacher(const string &s) { int n=s.size(); vector< int > radius(n); int i = 0, j = 0; while(i < n) { while(i - j >= 0 && i + j < n && s[i - j] == s[i + j]) { ++j; } radius[i] = j; int k = 1; while(i - k >= 0 && i + k < n && k + radius[i - k] < j) { radius[i + k] = radius[i - k]; ++k; } i += k; j -= k; } return radius; } struct RollingHash{ using ull=unsigned long long; const ull mask30=(1ll<<30)-1; const ull mask31=(1ll<<31)-1; const ull mod=(1ll<<61)-1; const ull positivizer=(mod<<2); ull calcmod(ull x){ ull ret=(x>>61)+(x&mod); if(ret>=mod) ret-=mod; return ret; } ull mul(ull a, ull b){ ull au=(a>>31), ad=(a&mask31), bu=(b>>31), bd=(b&mask31); ull mid=au*bd+ad*bu; ull midu=(mid>>30), midd=(mid&mask30); ull ret=((au*bu)<<1)+midu+(midd<<31)+ad*bd; //ret<2^63 return ret; } vector hash, power; RollingHash(const string &s, ull base=1000000007){ int sz=s.size(); hash.resize(sz+1); power.resize(sz+1); power[0]=1; for(int i=0; i>s[0]>>s[1]; unordered_map mps[2]; for(int z=0; z<2; z++){ int n=s[z].size(); string s1="#"; for(int i=0; i>> ss(n+1); for(int i=0; i>1); int l=i-u+1, r=i+u; ll x=rs.get(l, r); if(mps[z].find(x)==mps[z].end()) ss[r-l].push_back({l, x}); mps[z][x]++; if(i==n-1) break; u=(vs[(i<<1)+2]>>1); if(u==0) continue; l=i-u+1, r=i+1+u; x=rs.get(l, r); if(mps[z].find(x)==mps[z].end()) ss[r-l].push_back({l, x}); mps[z][x]++; } for(int d=n; d>=3; d--){ for(auto p:ss[d]){ int l=p.first; ll x0=p.second; ll x=rs.get(l+1, l+d-1); if(mps[z].find(x)==mps[z].end()) ss[d-2].push_back({l+1, x}); mps[z][x]+=mps[z][x0]; } } } ll ans=0; for(auto p:mps[0]){ ll x=p.first; if(mps[1].find(x)!=mps[1].end()){ ans+=mps[1][x]*p.second; } } cout<