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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

struct SuffixArray {
  struct SAComp {
    const int h, *g;
    SAComp(int h, int *g) : h(h), g(g) {;}
    bool operator() (int a, int b) {
      return a == b ? false : g[a] != g[b] ? g[a] < g[b] : g[a + h] < g[b + h];
    }
  };

  static const int SIZE = 200100;
  int n;
  char str[SIZE];
  vector<int> sa;
  vector<int> lcp;

  SuffixArray() {;}
  SuffixArray(char *t) {
    strcpy(str, t);
    Init();
  }
  void Init() {
    n = strlen(str);
    buildSA();
    buildLCP();
  }

  // O(mlogn)
  int find(char *p) {
    int m = strlen(p);
    int left = 0;
    int right = n;
    while (left < right) {
      int mid = (left + right) / 2;
      if (strncmp(str + sa[mid], p, m) < 0) { left = mid + 1; }
      else { right = mid; }
    }
    return strncmp(str + sa[left], p, m) == 0 ? sa[left] : -1;
  }
private:
  //O(nlog^2n)
  void buildSA() {
    sa = vector<int>(n + 1);
    int g[n + 1];
    int b[n + 1];
    REP(i, n + 1) { sa[i] = i; g[i] = str[i]; }
    b[0] = 0;
    b[n] = 0;

    sort(sa.begin(), sa.end(), SAComp(0, g));
    for (int h = 1; b[n] != n; h *= 2) {
      SAComp comp(h, g);
      sort(sa.begin(), sa.end(), comp);
      REP(i, n) b[i + 1] = b[i] + comp(sa[i], sa[i + 1]);
      REP(i, n + 1) g[sa[i]] = b[i];
    }
  }
  void buildLCP() {
    lcp = vector<int>(n + 1);
    int h = 0;
    int b[n + 1];
    REP(i, n + 1) { b[sa[i]] = i; }
    REP(i, n + 1) {
      if (b[i]) {
        for (int j = sa[b[i] - 1]; j + h < n && i + h < n && str[j + h] == str[i + h]; h++) {;}
        lcp[b[i]] = h;
      } else {
        lcp[b[i]] = -1;
      }
      if (h > 0) { h--; }
    }
  }
};

typedef int Node;
inline Node merge(Node left, Node right) {
  return min(left, right);
}

struct SegmentTree {
  static const int MAX_DEPTH = 18;  // 2^18 = 262144
  static const int SIZE = 1 << (MAX_DEPTH + 1);

  Node data[SIZE];
  void change(int index, Node value) {
    int target = (1 << MAX_DEPTH) + index;
    data[target] = value;
    for (int i = 1; i <= MAX_DEPTH; i++) {
      target >>= 1;
      data[target] = merge(data[target * 2], data[target * 2 + 1]);
    }
  }
  Node get(int left, int right) {
    assert(left <= right);
    return in_get(0, 1, left, right);
  }
private:
  Node in_get(int depth, int node, int left, int right) {
    int width = 1 << (MAX_DEPTH - depth);
    int index = node - (1 << depth);
    int node_left = index * width;
    int node_mid = node_left + (width >> 1);
    if (right - left + 1 == width && left == node_left) {
      return data[node];
    } else if (right < node_mid) {
      return in_get(depth + 1, node * 2, left, right);
    } else if (left >= node_mid) {
      return in_get(depth + 1, node * 2 + 1, left, right);
    }
    return merge(in_get(depth + 1, node * 2, left, node_mid - 1), in_get(depth + 1, node * 2 + 1, node_mid, right));
  }
};


struct UnionFind {
  int parent[200100];
  ll as[200100];
  ll bs[200100];
  UnionFind() {
    memset(parent, -1, sizeof(parent));
    MEMSET(as, 0);
    MEMSET(bs, 0);
  }
  ll unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) { return 0; }
    if (parent[y] < parent[x]) { swap(x, y); }
    ll ret = -as[x] * bs[x] - as[y] * bs[y];
    ll na = as[x] + as[y];
    ll nb = bs[x] + bs[y];
    ret += na * nb;
    as[x] = na;
    bs[x] = nb;
    as[y] = -1;
    bs[y] = -1;
    parent[x] += parent[y];
    parent[y] = x;
    return ret;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
  ll Add(int x, int type) {
    x = root(x);
    ll ret = -as[x] * bs[x];
    if (type == 0) {
      as[x]++;
    } else {
      bs[x]++;
    }
    ret += as[x] * bs[x];
    return ret;
  }
};

enum {
  MERGE,
  KAIBUN
};
struct Event {
  int type;
  int k;
  int info1;
  int info2;
  Event() {;}
  Event(int type, int k, int info1, int info2) : type(type), k(k), info1(info1), info2(info2) {;}
  bool operator<(const Event &rhs) const {
    return k < rhs.k;
  }
};

SuffixArray sa;
SegmentTree stree;
UnionFind ufind;
char str[2][50010];
int len[2];
int revsa[200010];

inline int Index(int type, int index, int rev) {
  int ret = 0;
  if (type == 1) { ret += len[0] * 2 + 2; }
  if (rev == 0) { ret += index; }
  else {
    ret += len[type] + 1 + (len[type] - index - 1);
  }
  return ret;
}

int main() {
  while (scanf("%s %s", str[0], str[1]) > 0) {
    sa.str[0] = 0;
    len[0] = strlen(str[0]);
    len[1] = strlen(str[1]);
    sprintf(sa.str + strlen(sa.str), "%s:", str[0]);
    reverse(str[0], str[0] + len[0]);
    sprintf(sa.str + strlen(sa.str), "%s;", str[0]);
    reverse(str[0], str[0] + len[0]);
    sprintf(sa.str + strlen(sa.str), "%s<", str[1]);
    reverse(str[1], str[1] + len[1]);
    sprintf(sa.str + strlen(sa.str), "%s>", str[1]);
    reverse(str[1], str[1] + len[1]);
    sa.Init();
    priority_queue<Event> que;
    ll ans = 0;
    REP(iter, 2) {
      ufind = UnionFind();
      MEMSET(stree.data, 0);
      REP(i, sa.n + 1) {
        stree.change(i, sa.lcp[i]);
        revsa[sa.sa[i]] = i;
        que.push(Event(MERGE, sa.lcp[i], i - 1, i));
        //cout << sa.lcp[i] << " ";
      }
      //cout << endl;
      REP(type, 2) {
        REP(i, len[type]) {
          if (iter == 0) {
            // odd
            int l = revsa[Index(type, i, 0)];
            int r = revsa[Index(type, i, 1)];
            if (l > r) { swap(l, r); }
            assert(l < r);
            int k = stree.get(l + 1, r);
            assert(k >= 1);
            que.push(Event(KAIBUN, k, l, type));
          } else {
            // even
            if (i == len[type] - 1) { continue; }
            int l = revsa[Index(type, i + 1, 0)];
            int r = revsa[Index(type, i, 1)];
            if (l > r) { swap(l, r); }
            assert(l < r);
            int k = stree.get(l + 1, r);
            if (k == 0) { continue; }
            que.push(Event(KAIBUN, k, l, type));
          }
        }
      }

      ll sum = 0;
      for (int k = sa.n; k > 0; k--) {
        while (que.top().k == k) {
          Event e = que.top();
          que.pop();
          if (e.type == MERGE) {
            sum += ufind.unionSet(e.info1, e.info2);
          } else {
            sum += ufind.Add(e.info1, e.info2);
          }
        }
        ans += sum;
        // cout << k << " " << ans << endl;
        // REP(i, sa.n) {
        //   cout << ufind.as[ufind.root(i)] << " ";
        // }
        // cout << endl;
        // REP(i, sa.n) {
        //   cout << ufind.bs[ufind.root(i)] << " ";
        // }
        // cout << endl;
      }
    }
    printf("%lld\n", ans);
  }
}