#include using namespace std; struct PalindromicTree{ struct node{ map nxt; int len,suf,hei,app,cnt; }; vector v; vector ord; int n,suff; PalindromicTree(){} PalindromicTree(const string &s){init(s);build(s);} bool addchar(const string &s,int pos){ char ch=s[pos]; int cur=suff; while(1){ if(pos-1-v[cur].len>=0&&s[pos-1-v[cur].len]==ch) break; cur=v[cur].suf; } if(v[cur].nxt.count(ch)){ suff=v[cur].nxt[ch]; v[suff].cnt++; return false; } suff=n++; v[suff].len=v[cur].len+2; v[suff].app=pos-v[suff].len+1; v[suff].cnt=1; v[cur].nxt[ch]=suff; if(v[suff].len==1){ v[suff].suf=1; v[suff].hei=1; return true; } while(1){ cur=v[cur].suf; if(pos-1-v[cur].len>=0&&s[pos-1-v[cur].len]==ch){ v[suff].suf=v[cur].nxt[ch]; break; } } v[suff].hei=v[v[suff].suf].hei+1; return true; } void init(const string &s){ v.resize(s.length()+10); n=2; suff=1; v[0].app=v[1].app=-1; v[0].len=-1;v[1].len=0; v[0].suf=v[1].suf=0; v[0].hei=v[1].hei=0; } void calcOrder(){ ord.clear(); ord.push_back(0); ord.push_back(1); for(int i=0;i<(int)ord.size();i++){ for(auto &p:v[ord[i]].nxt) ord.push_back(p.second); } } void calcCount(){ assert(ord.size()); for(int i=(int)ord.size()-1;i>=0;i--){ v[v[ord[i]].suf].cnt+=v[ord[i]].cnt; } v[0].cnt=v[1].cnt=0; } void build(const string &s){ for(int i=0;i<(int)s.size();i++) addchar(s,i); calcOrder(); calcCount(); ord.clear(); for(auto &x:v) x.nxt.clear(); v.resize(n); v.shrink_to_fit(); } }; struct RollingHash{ typedef unsigned int ull; ull B; vector hash; static vector p; RollingHash(){} RollingHash(const string &S,ull B=1777771):B(B){ int len=S.size(); hash.assign(len+1,0); ensure(len+1); for(int i=0;i=n) return; p.assign(n,1); for(int i=0;i+1 RollingHash::p; using ll = long long; using ull = RollingHash::ull; signed main(){ string s,t; cin>>s>>t; PalindromicTree p1(s),p2(t); RollingHash r1(s),r2(t); const int MAX = 5e5+100; map m1[MAX],m2[MAX]; for(int i=0;i<(int)p1.n;i++){ PalindromicTree::node& u=p1.v[i]; if(u.app<0) continue; m1[u.len][r1.find(u.app,u.app+u.len)]=u.cnt; } for(int i=0;i<(int)p2.n;i++){ PalindromicTree::node& u=p2.v[i]; if(u.app<0) continue; m2[u.len][r2.find(u.app,u.app+u.len)]=u.cnt; } ll ans=0; for(int i=1;i<=(int)s.length();i++) for(auto p:m1[i]) ans+=(ll)m2[i][p.first]*(ll)p.second; cout<