Problem: Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's practice is to improve the ability to read messages hidden from sentences by searching for palindromes in strings. There may be many palindromes, so I'd like to count the number while searching.

Given two strings S and T, we want to find the number of pairs of integers (i, j, k, l) that satisfy the following:

* 1 ≤ i ≤ j ≤ (length of S).
* 1 ≤ k ≤ l ≤ (length of T).
* The substrings extracted from the i-th to j-th characters of S are the same as the substrings extracted from the k-th to l-th characters of T, and these are palindromes (even when read from the left). It is a character string that is the same even when read from the right).



Input


S
T


Both the strings S and T have a length of 1 or more and 50,000 or less, and consist of uppercase letters.

Output

Output the number of pairs of integers (i, j, k, l) that satisfy the condition on one line.

Examples

Input

ICPC
CPCPC


Output

10


Input

BABBAB
ABBA


Output

14


Input

MYON
USAGI


Output

0

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <list>
#include <cmath>
#include <iomanip>
#define INF 0x3f3f3f3f
#define EPS 10e-5

typedef long long ll;
typedef unsigned long long ull;
const int dx[]={-1,0,0,1,0},dy[]={0,1,-1,0,0};
using namespace std;
int n,m,al;
const int maxn = 50005;
char a[maxn],b[maxn],c[maxn*2],ma[maxn*2];
int cnt[maxn*2],sa[maxn*2],lcp[maxn*2],mrank[maxn*2],
pn[maxn*2],cn[maxn*2],mlc[maxn*2],d[maxn*2];
pair<ll,ll> _st[maxn*5];
ll mpn[maxn*5];

struct mst{
    int now = -1;
    bool empty(){return now==-1;}
    void push(int first,int second){_st[++now] = pair<ll,ll>(first,second);}
    void pop(){--now;}
    void clear(){now = -1;}
    int size(){return now+1;}
    pair<ll,ll>& top() {return _st[now];}
};

struct ppa{
    int now = -1;
    bool empty(){return now == -1;}
    void push(ll first){mpn[++now] = first;}
    ll top(){return mpn[now];}
    void pop(){--now;}
    void clear(){now = -1;}
};

void build(){
    memset(cnt,0,sizeof(cnt));

    for(int i=0;i<al;++i)
        ++cnt[c[i]];
    for(int i=1;i<128;++i)
        cnt[i]+=cnt[i-1];
    for(int i=0;i<al;++i)
        sa[--cnt[c[i]]] = i;

    int last = 0;
    mrank[sa[0]] = 0;
    for(int i=1;i<al;++i){
        if(c[sa[i]] != c[sa[i-1]])
            ++last;
        mrank[sa[i]] = last;
    }

    for(int h=1;h<al;h<<=1){
        for(int i=0;i<al;++i){
            pn[i] = sa[i] - h;
            if(pn[i]<0)pn[i]+=al;
        }

    memset(cnt,0,sizeof(cnt));
    for(int i=0;i<al;++i)
        ++cnt[mrank[pn[i]]];
    for(int i=1;i<=last;++i)
        cnt[i]+=cnt[i-1];
    for(int i=al-1;i>=0;--i){
        sa[--cnt[mrank[pn[i]]]] = pn[i];
    }

        cn[sa[0]] = last = 0;
        for(int i=1;i<al;++i){
            if(mrank[sa[i]]!=mrank[sa[i-1]]||mrank[(sa[i]+h)%al]!=mrank[(sa[i-1]+h)%al])
                ++last;
            cn[sa[i]] = last;
        }
        memcpy(mrank,cn,sizeof(int)*al);
    }


      int h = 0;
      for(int i=0;i<al;++i)
          mrank[sa[i]] = i;

      for(int i=0;i<al;++i){
        if(mrank[i]==0) {
          h = 0;continue;
        }
        int j = sa[mrank[i]-1];

        if(h>0) --h;
        while(i+h<al&&j+h<al&&c[i+h]==c[j+h])++h;
            lcp[mrank[i]-1] = h;
      }
}

void manacher(char* ma,int* d,int le){
    int r = 0,l = -1,nd=0;
    for(int i=0;i<le;++i){
        if(i<l&&i>r){
            nd = min(l-i,d[r+(l-i)]);
        }else nd = 0;

        while(i-(nd+1)>=0&&i+(nd+1)<le&&ma[i+nd+1]==ma[i-nd-1])++nd;
        d[i] = nd;

        if(i+nd>l){
            l = i+nd;r=i-nd;
        }
    }
}

ll solve(){
    ll res = 0;
    mst st;
    ppa pa;
    ll acnt = 0;
    build();
    for(int i=0;i<n;++i){
        ma[2*i] = '#';ma[2*i+1] = a[i];
    }
    ma[2*n] = '#';
    manacher(ma,d,2*n+1);

    for(int i=0;i<al-1;++i){
        if(sa[i]<n){
            if((st.empty()||lcp[i]>st.top().second)&&lcp[i]>0){ // add
                ll b = st.empty()?0:st.top().second,e = lcp[i]*2-1;
                //cout << b << " "<< e << endl;
                for(ll j = b;2*j<e;++j){
                    if(d[2*sa[i]+1+j]>=j)
                    {
                        pa.push(j*2);
                    }
                }
                st.push(1,lcp[i]);
                acnt += pa.now+1;
            }else if(!st.empty()&&lcp[i]==st.top().second){ //remove
                ++st.top().first;
                acnt += pa.now+1;
            }
            else{
                int fcnt = 0;
                //cout << st.now << " "<<i << endl;
                while(!st.empty()&&lcp[i]<=st.top().second){
                    int cnt = 0;
                    pair<ll,ll> now = st.top();
                    st.pop();
                    while(!pa.empty()&&pa.top()>=2*lcp[i]-1&&(st.empty()||pa.top()>=st.top().second*2-1)){
                        pa.pop();++cnt;
                    }
                    acnt -= cnt*(now.first+fcnt);
                    fcnt += now.first;
                    //if(!st.empty())st.top().first+=now.first;
                }
                //if(lcp[i]==0) continue;
                acnt+=pa.now+1;
                st.push(fcnt+1,lcp[i]);
            }
        }else if(!st.empty()&&lcp[i]<st.top().second){
            int lastFirst=0;
            while(!st.empty()&&lcp[i]<=st.top().second){
                int cnt = 0;
                pair<ll,ll> now = st.top();
                st.pop();
                while(!pa.empty()&&pa.top()>=2*lcp[i]-1&&(st.empty()||pa.top()>=st.top().second*2-1)){
                    pa.pop();++cnt;
                }
                acnt -= cnt*(now.first+lastFirst);
                lastFirst += now.first;
                //if(!st.empty()){st.top().first+=now.first;}
            }
            //if(lcp[i]==0) {continue;}
            st.push(lastFirst,lcp[i]);
            //if(!st.empty()) st.top().second = lcp[i];
        }


        //cout << "acnt:"<<acnt<< " " << endl;
        if(sa[i+1]>n) {res+=acnt;}
    }

    acnt = 0;st.clear();pa.clear();

    for(int i=0;i<m;++i){
        ma[2*i] = '#';ma[2*i+1] = b[i];
    }
    ma[2*m] = '#';
    manacher(ma,d,2*m+1);

    for(int i=0;i<al-1;++i){
        //cout << "res:"<<res<<" pa-size:"<<pa.now+1<<endl;
        if(sa[i]>n){
            if((st.empty()||lcp[i]>st.top().second)&&lcp[i]>0){ // add
                int b = st.empty()?0:st.top().second,e = lcp[i]*2-1;
                for(int j = b;2*j<e;++j){
                    if(d[2*(sa[i]-n-1)+1+j]>=j) pa.push(j*2);
                }
                st.push(1,lcp[i]);
                acnt += pa.now+1;
            }else if(!st.empty()&&lcp[i]==st.top().second){ //remove
                //cout << lcp[i] << " "<<pa.top() << endl;
                ++st.top().first;
                acnt += pa.now+1;
            }
            else{
                int fcnt = 0;
                //cout << st.now << " "<<i << endl;
                while(!st.empty()&&lcp[i]<=st.top().second){
                    int cnt = 0;
                    pair<ll,ll> now = st.top();
                    st.pop();
                    while(!pa.empty()&&pa.top()>=2*lcp[i]-1&&(st.empty()||pa.top()>=st.top().second*2-1)){
                        pa.pop();++cnt;
                    }
                    acnt -= cnt*(now.first+fcnt);
                    fcnt += now.first;
                    //if(!st.empty())st.top().first+=now.first;
                }
                acnt+=pa.now+1;
                st.push(fcnt+1,lcp[i]);
            }
        }else if(!st.empty()&&lcp[i]<st.top().second){
            int lastFirst=0;
            while(!st.empty()&&lcp[i]<=st.top().second){
                int cnt = 0;
                pair<ll,ll> now = st.top();
                st.pop();
                while(!pa.empty()&&pa.top()>=2*lcp[i]-1&&(st.empty()||pa.top()>=st.top().second*2-1)){
                    pa.pop();++cnt;
                }
                acnt -= cnt*(now.first+lastFirst);
                lastFirst += now.first;
                //if(!st.empty()){st.top().first+=now.first;}
            }
            st.push(lastFirst,lcp[i]);
            //if(!st.empty()) st.top().second = lcp[i];
        }

        //cout << "acnt:"<<acnt<< " " << pa.now+1<<endl;
        if(sa[i+1]<n) {res+=acnt;}
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    scanf("%s %s",a,b);
    n = strlen(a);m = strlen(b);
    memcpy(c,a,sizeof(char)*n);

    c[n] = '$';
    memcpy(c+n+1,b,sizeof(char)*m);
    c[n+m+1] = '$'-1;
    al = n+m+2;
    memset(mlc,0,sizeof(int)*al);
    printf("%lld\n",solve());
    return 0;
}