#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{ const ll mask30=(1ll<<30)-1; const ll mask31=(1ll<<31)-1; const ll mod=(1ll<<61)-1; ll mul(ll a, ll b){ ll au=(a>>31), ad=(a&mask31), bu=(b>>31), bd=(b&mask31); ll mid=au*bd+ad*bu; ll midu=(mid>>30), midd=(mid&mask30); ll ret=((au*bu)<<1)+midu+(midd<<31)+ad*bd; ret=(ret>>61)+(ret&mod); if(ret>=mod) ret-=mod; return ret; } vector hash, power; RollingHash(const string &s, ll base=1000000007){ int sz=s.size(); hash.resize(sz+1); power.resize(sz+1); power[0]=1; for(int i=0; i=mod) hash[i+1]-=mod; } } ll get(int l, int r){ // [l, r) ll ret=hash[r]+mod-mul(hash[l], power[r-l]); if(ret>=mod) ret-=mod; return ret; } ll concat(ll h1, ll h2, int len2){ //h1+h2 ll ret=mul(h1, power[len2])+h2; if(ret>=mod) ret-=mod; return ret; } }; int main() { string s[2]; cin>>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<