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 <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

/**
 * Suffix Array
 */

namespace SuffixArray {
    template<class T>
    void induce(int n, const T s[], bool ls[], int sa[], int l_basm[], int B) {
        int buf[B+10];
        copy_n(l_basm, B+1, buf);
        for (int i = 0; i <= n; i++) {
            if (sa[i] >= 1 && !ls[sa[i]-1]) {
                int bc = s[sa[i]-1];
                sa[buf[bc]++] = sa[i]-1;
            }
        }

        copy_n(l_basm, B+1, buf);
        for (int i = n; i > 0; i--) {
            if (sa[i] >= 1 && ls[sa[i]-1]) {
                int bc = s[sa[i]-1];
                sa[--buf[bc+1]] = sa[i]-1;
            }
        }
    }

    template<class T>
    void SA(int n, const T s[], int sa[], int B = 200) {
        bool ls[n+1]; //L:false S:true
        int l_ba[B+1], s_ba[B+1];
        fill_n(l_ba, B+1, 0); fill_n(s_ba, B+1, 0);
        ls[n] = true;
        for (int i = n-1; i >= 0; i--) {
            if (i == n-1 || s[i] > s[i+1]) {
                ls[i] = false;
            } else if (s[i] < s[i+1]) {
                ls[i] = true;
            } else {
                ls[i] = ls[i+1];
            }
            if (!ls[i]) {
                l_ba[(int)s[i]]++;
            } else {
                s_ba[(int)s[i]]++;
            }
        }

        vector<int> v;
        int lms[n+1];
        fill_n(lms, n+1, -1);
        int c = 0;
        for (int i = 1; i < n; i++) {
            if (!ls[i-1] && ls[i]) {
                lms[i] = c++;
                v.push_back(i);
            }
        }
        
        int l_basm[B+1], s_basm[B+1];
        l_basm[0] = 1; s_basm[0] = 1+l_ba[0];
        for (int i = 1; i <= B; i++) {
            l_basm[i] = s_basm[i-1]+s_ba[i-1];
            s_basm[i] = l_basm[i]+l_ba[i];
        }

        if (v.size()) {
            vector<int> v2 = v;
            int buf[B+1];
            copy_n(s_basm, B+1, buf);
            fill_n(sa, n+1, -1);
            sa[0] = n;
            for (int i = 0; i < (int)v.size(); i++) {
                int c = s[v[i]];
                sa[buf[c]++] = v[i];
            }
            induce(n, s, ls, sa, l_basm, B);
            int c = 0;
            for (int i = 1; i <= n; i++) {
                if (lms[sa[i]] == -1) continue;
                v[c++] = sa[i];
            }

            int s2[v.size()];
            int sa2[v.size()+1];
            c = 0;
            s2[lms[v[0]]] = 0;
            for (int i = 1; i < (int)v.size(); i++) {
                int l = v[i-1], r = v[i];
                while (true) {
                    if (s[l] != s[r]) {
                        c++;
                        break;
                    }
                    l++; r++;
                    if (lms[l] != -1 || lms[r] != -1) {
                        if (lms[l] == -1 || lms[r] == -1) {
                            c++;
                        }
                        break;
                    }
                }
                s2[lms[v[i]]] = c;
            }
            SA(v.size(), s2, sa2, c);
            for (int i = 1; i <= (int)v.size(); i++) {
                v[i-1] = v2[sa2[i]];
            }
        }

        int buf[B+1];
        copy_n(s_basm, B+1, buf);

        fill_n(sa, n+1, -1);
        sa[0] = n;
        for (int i = 0; i < (int)v.size(); i++) {
            int c = s[v[i]];
            sa[buf[c]++] = v[i];
        }

        induce(n, s, ls, sa, l_basm, B);
    }

    template <class T>
    void LCP(int n, const T s[], const int sa[], int lcp[]) {
        int rsa[n+1];
        for (int i = 0; i <= n; i++) {
            rsa[sa[i]] = i;
        }
        int h = 0;
        for (int i = 0; i < n; i++) {
            int j = sa[rsa[i]-1];

            if (h > 0) h--;
            for (; j+h < n && i+h < n; h++) {
                if (s[j+h] != s[i+h]) break;
            }
            lcp[rsa[i]-1] = h;
        }
    }
}

//binary search reverse
int bsr(int x) {
    return 31 - __builtin_clz(x);
}

template<int S>
struct SparseRMQ {
    static const int N = 1<<S;
    int d[S][N];
    void init() {
        int l = 1;
        for (int s = 1; s < S; s++) {
            for (int i = 0; i < N - l; i++) {
                d[s][i] = min(d[s-1][i], d[s-1][i + l]);
            }
            l <<= 1;
        }
    }
    int query(int l, int r) {
        assert(l <= r);
        if (l == r) return 1<<28;
        int u = bsr(r-l);
        return min(d[u][l], d[u][r-(1<<u)]);
    }
};

template<int S>
struct SparseLMRMQ {
    static const int N = 1<<S;
    static const int T = 5;
    static const int B = 1<<T;
    SparseRMQ<S-T> sq;
    int d[N];
    void init() {
        for (int i = 0; i < N/B; i++) {
            int res = 1<<28;
            for (int j = 0; j < B; j++) {
                res = min(res, d[i*B+j]);
            }
            sq.d[0][i] = res;
        }
        sq.init();
    }
    int query(int l, int r) {
        int lb = (l+B-1)/B, rb = r/B;
        int res = 1<<28;
        if (lb > rb) {
            for (int i = l; i < r; i++) {
                res = min(res, d[i]);
            }
            return res;
        }

        while (l % B) {
            res = min(res, d[l]);
            l++;
        }
        while (r % B) {
            r--;
            res = min(res, d[r]);
        }
        res = min(res, sq.query(lb, rb));
        return res;
    }
};

//    void SA(int n, const T s[], int sa[], int B = 200) {
//    void LCP(int n, const T s[], const int sa[], int lcp[]) {

const int MN = 200100;

int n, m;
string s, t;
SparseLMRMQ<18> slcp, tlcp;

const int HBS = 6;
static ll B[] = {(ull)1e9+7, (ull)1e9+9, (ull)1e9+13, (ull)1e9+17, (ull)1e9+31, (ull)1e9+51};
static ll MD[] = {380299448, 498272334, 480228843, 852703, 8979287, 43402840};
using HS = array<ll, HBS>;
static HS pmd[MN+1];
static HS shs[MN], ths[MN];
static int ssa[MN], tsa[MN];
static int srsa[MN], trsa[MN];

void init() {
    n = (int)s.size();
    t = s + '~' + t;
    m = (int)t.size();
    pmd[0].fill(1);
    for (int i = 1; i <= MN; i++) {
        for (int j = 0; j < HBS; j++) {
            pmd[i][j] = pmd[i-1][j] * MD[j];
            pmd[i][j] %= B[j];
        }
    }
    shs[0].fill(0);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < HBS; j++) {
            shs[i][j] = shs[i-1][j] + s[i-1] * pmd[i-1][j];
            shs[i][j] %= B[j];
        }
    }
    ths[0].fill(0);
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < HBS; j++) {
            ths[i][j] = ths[i-1][j] + t[i-1] * pmd[i-1][j];
            ths[i][j] %= B[j];
        }
    }

    SuffixArray::SA(n, s.c_str(), ssa);
    SuffixArray::SA(m, t.c_str(), tsa);
    for (int i = 0; i <= n; i++) {
        srsa[ssa[i]] = i;
    }
    for (int i = 0; i <= m; i++) {
        trsa[tsa[i]] = i;
    }
    SuffixArray::LCP(n, s.c_str(), ssa, slcp.d);
    SuffixArray::LCP(m, t.c_str(), tsa, tlcp.d);
    slcp.init();
    tlcp.init();
}

HS geths(HS hs[], int l, int r) {
    HS res;
    res.fill(0);
    for (int j = 0; j < HBS; j++) {
        res[j] = (hs[r][j] - hs[l][j]) * pmd[MN-r][j];
        res[j] = (res[j]%B[j] + B[j]) % B[j];
    }
//    return (hs[r] - hs[l]) * pmd[MN - r] % B;
    return res;
}

int counts(int x, int sz) {
    int f = srsa[x];
    int a, b;
    int l = -1, r = f;
    while (r-l > 1) {
        int md = (l+r)/2;
        if (slcp.query(md, f) < sz) {
            l = md;
        } else {
            r = md;
        }
    }
    a = r;
    l = f, r = n+1;
    while (r-l > 1) {
        int md = (l+r)/2;
        if (slcp.query(f, md) >= sz) {
            l = md;
        } else {
            r = md;
        }
    }
    b = r;
    return b - a;
}

int countt(int x, int sz) {
    int f = trsa[x];
    int a, b;
    int l = -1, r = f;
    while (r-l > 1) {
        int md = (l+r)/2;
        if (tlcp.query(md, f) < sz) {
            l = md;
        } else {
            r = md;
        }
    }
    a = r;
    l = f, r = m+1;
    while (r-l > 1) {
        int md = (l+r)/2;
        if (tlcp.query(f, md) >= sz) {
            l = md;
        } else {
            r = md;
        }
    }
    b = r;
    return b - a;
}

int main() {
    string s0, t0;
    cin >> s0 >> t0;

    s = "$"; t = "$";
    for (char c: s0) {
        s += c;
        s += '$';
    }
    for (char c: t0) {
        t += c;
        t += '$';
    }
    init();
    set<HS> table;
    vector<P> v;
    static int R[MN];
    for (int i = 0, j = 0; i < n; i++) {
        int &k = R[i]; k = min(j+R[j]-i, R[2*j-i]);
        while (0 <= i-k and i+k < n and s[i-k] == s[i+k]) {
            k++;
            if (s[i-k+1] != '$' && !table.count(geths(shs, i-k+1, i+k))) {
                table.insert(geths(shs, i-k+1, i+k));
                v.push_back(P(i-k+1, i+k));
            }
        }
        if (j + R[j] < i + R[i]) j = i;
    }
//    cout << v.size() << endl;
    ll sm = 0;
    for (P p: v) {
//        printf("%d %d\n", p.first, p.second);
//        printf("%s\n", s.substr(p.first, p.second-p.first).c_str());
        int cs = counts(p.first, p.second - p.first);
        int ct = countt(p.first, p.second - p.first) - cs;
//        printf("%d %d\n", cs, ct);
        sm += (ll)cs * ct;
    }
    cout << sm << endl;
    return 0;
}