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 <string>
#include <cstring>
#include <map>
#include <algorithm>
 
using namespace std;
typedef long long LL;
 
struct SA
{
    static const int N = 200000; // len+1<=N
    int a[N], lcp[N];
 
    void build(const string &s)
    { build(s.c_str(), s.size()); }
 
    void build(const char *t, int n)
    {
        // suffix array
        static int g[N], b[N];
        for (int i = 0; i < n + 1; ++i)
        {
            a[i] = i, g[i] = t[i];
        }
        b[0] = b[n] = 0;
        sort(a, a + n + 1, SAComp(0, g));
        for (int h = 1; b[n] != n; h *= 2)
        {
            SAComp comp(h, g);
            sort(a, a + n + 1, comp);
            for (int i = 0; i < n; ++i)
            {
                b[i + 1] = b[i] + comp(a[i], a[i + 1]);
            }
            for (int i = 0; i < n + 1; ++i)
            {
                g[a[i]] = b[i];
            }
        }
        // longest common prefix (you can omit here)
        for (int i = 0; i < n + 1; ++i)
        {
            b[a[i]] = i;
        }
        int h = 0;
        for (int i = 0; i < n; ++i)
        {
            const int j = a[b[i] - 1];
            while (j + h < n && i + h < n && t[j + h] == t[i + h])
                h++;
            lcp[b[i]] = h;
            if (h)
                h--;
        }
        lcp[0] = -1;
    }
 
    struct SAComp
    {
        const int h, *g;
 
        SAComp(int h, int *g) : h(h), g(g)
        {}
 
        bool operator()(int l, int r)
        {
            return g[l] != g[r] ? g[l] < g[r] : g[l + h] < g[r + h];
        }
    };
} sa;
 
struct Manacher
{
    static const int N = 200000 * 2; // len*2
    int rad[N];
 
    void build(const string &s)
    { build(s.c_str(), s.size()); }
 
    void build(const char *t, int n)
    {
        int k;
        for (int i = 0, j = 0; i < 2 * n; i += k, j = max(j - k, 0))
        {
            while (i - j >= 0 && i + j + 1 < 2 * n && t[(i - j) / 2] == t[(i + j + 1) / 2])
                j++;
            rad[i] = j;
            for (k = 1; i - k >= 0 && rad[i] - k >= 0 && rad[i - k] != rad[i] - k; k++)
            {
                rad[i + k] = min(rad[i - k], rad[i] - k);
            }
        }
    }
} mana;
 
struct BIT
{
    static const int N = 80000;
    LL x[N];
 
    void init()
    { memset(x, 0, sizeof(x)); }
 
    void add(int k, LL a)
    {
        for (; k < N; k |= k + 1)
            x[k] += a;
    }
 
    LL sum(int k)
    {
        LL s = 0;
        for (; k >= 0; k = (k & (k + 1)) - 1)
            s += x[k];
        return s;
    }
 
    LL rsum(int i, int j)
    { return i == 0 ? sum(j) : sum(j) - sum(i - 1); }
 
    LL esum(int i)
    { return rsum(i, N - 1); }
} sum[2], cnt[2];
 
int of[200000];
 
int main()
{
    string S, T;
    cin >> S >> T;
    const string F(S + '$' + T);
    sa.build(F);
    mana.build(F);
    for (int i = 0; i < F.size() + 1; ++i)
    {
        of[i] = sa.a[i] > (int) S.size();
    }
 
    LL ans = 0;
    for (int odd = 0; odd < 2; ++odd)// 回文长度是否为奇数
    {
        for (int i = 0; i < 2; ++i)
            sum[i].init(), cnt[i].init();
        map<int, int> palindrome[2];// AB各自的回文子串半径plen的个数
        for (int k = 1; k < (int) F.size() + 1; k++)
        {
            const int clen = sa.lcp[k];// 公共子串的长度
            for (int i = 0; i < 2; ++i)
            {
                map<int, int>::iterator it = palindrome[i].lower_bound(clen + 1);
                while (it != palindrome[i].end())// 遍历半径大于公共子串clen的回文子串
                {//维护Binary Indexed Tree
                    const int plen = it->first, p = it->second;// 回文子串长度及个数
                    sum[i].add(plen, -(LL) plen * p);//在[clen,plen]区间同时加上p
                    cnt[i].add(plen, -p);
                    sum[i].add(clen, (LL) clen * p);
                    cnt[i].add(clen, p);
                    palindrome[i][clen] += p;
                    palindrome[i].erase(it++);
                }
            }// 在sa[k]位置的回文半径
            const int plen = odd ? mana.rad[sa.a[k] * 2] / 2 + 1 : sa.a[k] ? mana.rad[sa.a[k] * 2 - 1] / 2 : 0;
            ans += sum[1 - of[k]].sum(plen) + (LL) plen * cnt[1 - of[k]].esum(plen + 1);//前plen项之和
            sum[of[k]].add(plen, plen); // a[plen] += 1
            cnt[of[k]].add(plen, 1);
            palindrome[of[k]][plen]++;
        }
    }
    cout << ans << endl;
    return 0;
}