#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 200000 + 5;
const int seed = 135;
const int p1 = 1e9 + 7, p2 = 1e9 + 9;
unsigned long long xp1[maxn], xp2[maxn], xp[maxn];
struct Hash {
  static void init() {
    xp1[0] = xp2[0] = xp[0] = 1;
    for (int i = 1; i < maxn; ++i) {
      xp1[i] = xp1[i - 1] * seed % p1;
      xp2[i] = xp2[i - 1] * seed % p2;
      xp[i] = xp[i - 1] * seed;
    }
  }
  unsigned long long h[maxn];
  unsigned long long build(int n, const char* s) {
    unsigned long long r1 = 0, r2 = 0;
    for (int i = 1; i <= n; i++) {
      r1 = (r1 * seed + s[i]) % p1;
      r2 = (r2 * seed + s[i]) % p2;
      h[i] = (r1 << 32) | r2;
    }
    return h[n];
  }
  unsigned long long query(int l, int r) {
    int len = r - l + 1;
    unsigned int mask32 = ~(0u);
    unsigned long long left1 = h[l - 1] >> 32, right1 = h[r] >> 32;
    unsigned long long left2 = h[l - 1] & mask32, right2 = h[r] & mask32;
    return (((right1 - left1 * xp1[len] % p1 + p1) % p1) << 32) |
           (((right2 - left2 * xp2[len] % p2 + p2) % p2));
  }
} hs, ht;
unsigned long long offset(unsigned long long a, unsigned long long b, int len) {
  unsigned int mask32 = ~(0u);
  unsigned long long a1 = a >> 32, a2 = a & mask32;
  unsigned long long b1 = b >> 32, b2 = b & mask32;
  return (((b1 + a1 * xp1[len] % p1) % p1) << 32) |
         ((b2 + a2 * xp2[len] % p2) % p2);
}
struct pam {
  int sz, tot, last;
  int ch[maxn][26], len[maxn], fail[maxn];
  int dif[maxn], slink[maxn];
  int cnt[maxn], dep[maxn], pos[maxn], pnode[maxn];
  char s[maxn];
  int node(int l) {
    sz++;
    memset(ch[sz], 0, sizeof(ch[sz]));
    len[sz] = l;
    fail[sz] = cnt[sz] = dep[sz] = 0;
    return sz;
  }
  void clear() {
    sz = -1;
    last = 0;
    s[tot = 0] = '$';
    node(0);
    node(-1);
    fail[0] = 1;
  }
  int getfail(int x) {
    while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
    return x;
  }
  int insert(char c) {
    s[++tot] = c;
    int now = getfail(last);
    if (!ch[now][c - 'a']) {
      int x = node(len[now] + 2);
      fail[x] = ch[getfail(fail[now])][c - 'a'];
      dep[x] = dep[fail[x]] + 1;
      ch[now][c - 'a'] = x;
      dif[x] = len[x] - len[fail[x]];
      if (dif[x] == dif[fail[x]])
        slink[x] = slink[fail[x]];
      else
        slink[x] = fail[x];
    }
    last = ch[now][c - 'a'];
    cnt[last]++;
    return last;
  }
  void build(int n, const char* s) {
    clear();
    for (int i = 1; i <= n; i++) {
      int u = insert(s[i]);
      pos[u] = i;
      pnode[i] = u;
    }
  }
  int get(int u, int ql) {
    if (ql > len[u]) return len[u];
    while (true) {
      int l = len[slink[u]];
      int d = dif[u];
      if (ql >= l) {
        return ((ql - l) / d) * d + l;
      }
      u = slink[u];
    }
    return 0;
  }
} ps, pt, psr, ptr;
char s[maxn], t[maxn];
int slen, tlen;
bool checkPad(int l, int r, pam& p) {
  return p.get(p.pnode[r], r - l + 1) == r - l + 1;
}
int checkDec(int l, int r, pam& p, pam& pr) {
  int a = p.get(p.pnode[r], r - l + 1);
  if (l <= r - a && r - a + 1 <= r && checkPad(l, r - a, p)) {
    return r - a - l + 1;
  }
  a = pr.get(pr.pnode[pr.tot - l + 1], r - l + 1);
  if (l <= l + a - 1 && l + a <= r && checkPad(l + a, r, p)) {
    return a;
  }
  return -1;
}
int main() {
  Hash::init();
  scanf("%s%s", s + 1, t + 1);
  slen = strlen(s + 1);
  tlen = strlen(t + 1);
  ps.build(slen, s);
  hs.build(slen, s);
  pt.build(tlen, t);
  ht.build(tlen, t);
  reverse(s + 1, s + slen + 1);
  reverse(t + 1, t + tlen + 1);
  psr.build(slen, s);
  ptr.build(tlen, t);
  long long ans = 1ll * (ps.sz - 1) * (pt.sz - 1);
  map<unsigned long long, int> padmps, padmpt;
  map<unsigned long long, int> mps, mpt;
  for (int i = 2; i <= ps.sz; i++) {
    padmps[hs.query(ps.pos[i] - ps.len[i] + 1, ps.pos[i])]++;
    int p = ps.fail[i];
    if (p <= 1) continue;
    if (ps.len[i] <= ps.len[p] * 2) {
      int l = ps.pos[i] - (ps.len[i] - ps.len[p]) + 1;
      int r = ps.pos[i];
      mps[hs.query(l, r)]++;
    }
  }
  for (int i = 2; i <= pt.sz; i++) {
    padmpt[ht.query(pt.pos[i] - pt.len[i] + 1, pt.pos[i])]++;
    int p = pt.fail[i];
    if (p <= 1) continue;
    if (pt.len[i] <= pt.len[p] * 2) {
      int l = pt.pos[i] - pt.len[i] + 1;
      int r = l + (pt.len[i] - pt.len[p]) - 1;
      mpt[ht.query(l, r)]++;
    }
  }
  for (int i = 2; i <= ps.sz; i++) {
    int p = ps.fail[i];
    if (p <= 1) continue;
    int l = ps.pos[i] - (ps.len[i] - ps.len[p]) + 1;
    int r = ps.pos[i];
    unsigned long long h = hs.query(l, r);
    if (mpt.count(h)) ans -= mpt[h];
    int plen = checkDec(l, r, ps, psr);
    if (plen != -1) {
      unsigned long long pw = hs.query(l, l + plen - 1);
      unsigned long long wt = offset(h, pw, plen);
      if (padmpt.count(pw) && padmpt.count(wt)) {
        ans--;
      }
    }
  }
  for (int i = 2; i <= pt.sz; i++) {
    int p = pt.fail[i];
    if (p <= 1) continue;
    int l = pt.pos[i] - pt.len[i] + 1;
    int r = l + (pt.len[i] - pt.len[p]) - 1;
    unsigned long long h = ht.query(l, r);
    if (mps.count(h)) ans -= mps[h];
    int plen = checkDec(l, r, pt, ptr);
    if (plen != -1) {
      unsigned long long pw = ht.query(l + plen, r);
      unsigned long long tw = offset(pw, h, r - l + 1);
      if (padmps.count(pw) && padmps.count(tw)) {
        ans--;
      }
    }
  }
  for (int i = 2; i <= ps.sz; i++) {
    int p = ps.fail[i];
    if (p <= 1) continue;
    if (ps.len[i] > ps.len[p] * 2) {
      int l = ps.pos[i] - (ps.len[i] - ps.len[p]) + 1;
      int r = ps.pos[i];
      mps[hs.query(l, r)]++;
    }
  }
  for (int i = 2; i <= pt.sz; i++) {
    int p = pt.fail[i];
    if (p <= 1) continue;
    if (pt.len[i] > pt.len[p] * 2) {
      int l = pt.pos[i] - pt.len[i] + 1;
      int r = l + (pt.len[i] - pt.len[p]) - 1;
      mpt[ht.query(l, r)]++;
    }
  }
  for (auto& x : mps) {
    ans += 1ll * x.second * mpt[x.first];
  }
  printf("%I64d\n", ans);
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

After learning some fancy algorithms about palindromes, Chouti found palindromes very interesting, so he wants to challenge you with this problem.

Chouti has got two strings A and B. Since he likes [palindromes](https://en.wikipedia.org/wiki/Palindrome), he would like to pick a as some non-empty palindromic substring of A and b as some non-empty palindromic substring of B. Concatenating them, he will get string ab.

Chouti thinks strings he could get this way are interesting, so he wants to know how many different strings he can get.

Input

The first line contains a single string A (1 ≤ |A| ≤ 2 ⋅ 10^5).

The second line contains a single string B (1 ≤ |B| ≤ 2 ⋅ 10^5).

Strings A and B contain only lowercase English letters.

Output

The first and only line should contain a single integer — the number of possible strings.

Examples

Input

aa
aba


Output

6


Input

aaba
abaa


Output

15

Note

In the first example, attainable strings are 

  * "a" + "a" = "aa", 
  * "aa" + "a" = "aaa", 
  * "aa" + "aba" = "aaaba", 
  * "aa" + "b" = "aab", 
  * "a" + "aba" = "aaba", 
  * "a" + "b" = "ab". 



In the second example, attainable strings are "aa", "aaa", "aaaa", "aaaba", "aab", "aaba", "ab", "abaa", "abaaa", "abaaba", "abab", "ba", "baa", "baba", "bb".

Notice that though "a"+"aa"="aa"+"a"="aaa", "aaa" will only be counted once.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 200000 + 5;
const int seed = 135;
const int p1 = 1e9 + 7, p2 = 1e9 + 9;
unsigned long long xp1[maxn], xp2[maxn], xp[maxn];
struct Hash {
  static void init() {
    xp1[0] = xp2[0] = xp[0] = 1;
    for (int i = 1; i < maxn; ++i) {
      xp1[i] = xp1[i - 1] * seed % p1;
      xp2[i] = xp2[i - 1] * seed % p2;
      xp[i] = xp[i - 1] * seed;
    }
  }
  unsigned long long h[maxn];
  unsigned long long build(int n, const char* s) {
    unsigned long long r1 = 0, r2 = 0;
    for (int i = 1; i <= n; i++) {
      r1 = (r1 * seed + s[i]) % p1;
      r2 = (r2 * seed + s[i]) % p2;
      h[i] = (r1 << 32) | r2;
    }
    return h[n];
  }
  unsigned long long query(int l, int r) {
    int len = r - l + 1;
    unsigned int mask32 = ~(0u);
    unsigned long long left1 = h[l - 1] >> 32, right1 = h[r] >> 32;
    unsigned long long left2 = h[l - 1] & mask32, right2 = h[r] & mask32;
    return (((right1 - left1 * xp1[len] % p1 + p1) % p1) << 32) |
           (((right2 - left2 * xp2[len] % p2 + p2) % p2));
  }
} hs, ht;
unsigned long long offset(unsigned long long a, unsigned long long b, int len) {
  unsigned int mask32 = ~(0u);
  unsigned long long a1 = a >> 32, a2 = a & mask32;
  unsigned long long b1 = b >> 32, b2 = b & mask32;
  return (((b1 + a1 * xp1[len] % p1) % p1) << 32) |
         ((b2 + a2 * xp2[len] % p2) % p2);
}
struct pam {
  int sz, tot, last;
  int ch[maxn][26], len[maxn], fail[maxn];
  int dif[maxn], slink[maxn];
  int cnt[maxn], dep[maxn], pos[maxn], pnode[maxn];
  char s[maxn];
  int node(int l) {
    sz++;
    memset(ch[sz], 0, sizeof(ch[sz]));
    len[sz] = l;
    fail[sz] = cnt[sz] = dep[sz] = 0;
    return sz;
  }
  void clear() {
    sz = -1;
    last = 0;
    s[tot = 0] = '$';
    node(0);
    node(-1);
    fail[0] = 1;
  }
  int getfail(int x) {
    while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
    return x;
  }
  int insert(char c) {
    s[++tot] = c;
    int now = getfail(last);
    if (!ch[now][c - 'a']) {
      int x = node(len[now] + 2);
      fail[x] = ch[getfail(fail[now])][c - 'a'];
      dep[x] = dep[fail[x]] + 1;
      ch[now][c - 'a'] = x;
      dif[x] = len[x] - len[fail[x]];
      if (dif[x] == dif[fail[x]])
        slink[x] = slink[fail[x]];
      else
        slink[x] = fail[x];
    }
    last = ch[now][c - 'a'];
    cnt[last]++;
    return last;
  }
  void build(int n, const char* s) {
    clear();
    for (int i = 1; i <= n; i++) {
      int u = insert(s[i]);
      pos[u] = i;
      pnode[i] = u;
    }
  }
  int get(int u, int ql) {
    if (ql > len[u]) return len[u];
    while (true) {
      int l = len[slink[u]];
      int d = dif[u];
      if (ql >= l) {
        return ((ql - l) / d) * d + l;
      }
      u = slink[u];
    }
    return 0;
  }
} ps, pt, psr, ptr;
char s[maxn], t[maxn];
int slen, tlen;
bool checkPad(int l, int r, pam& p) {
  return p.get(p.pnode[r], r - l + 1) == r - l + 1;
}
int checkDec(int l, int r, pam& p, pam& pr) {
  int a = p.get(p.pnode[r], r - l + 1);
  if (l <= r - a && r - a + 1 <= r && checkPad(l, r - a, p)) {
    return r - a - l + 1;
  }
  a = pr.get(pr.pnode[pr.tot - l + 1], r - l + 1);
  if (l <= l + a - 1 && l + a <= r && checkPad(l + a, r, p)) {
    return a;
  }
  return -1;
}
int main() {
  Hash::init();
  scanf("%s%s", s + 1, t + 1);
  slen = strlen(s + 1);
  tlen = strlen(t + 1);
  ps.build(slen, s);
  hs.build(slen, s);
  pt.build(tlen, t);
  ht.build(tlen, t);
  reverse(s + 1, s + slen + 1);
  reverse(t + 1, t + tlen + 1);
  psr.build(slen, s);
  ptr.build(tlen, t);
  long long ans = 1ll * (ps.sz - 1) * (pt.sz - 1);
  map<unsigned long long, int> padmps, padmpt;
  map<unsigned long long, int> mps, mpt;
  for (int i = 2; i <= ps.sz; i++) {
    padmps[hs.query(ps.pos[i] - ps.len[i] + 1, ps.pos[i])]++;
    int p = ps.fail[i];
    if (p <= 1) continue;
    if (ps.len[i] <= ps.len[p] * 2) {
      int l = ps.pos[i] - (ps.len[i] - ps.len[p]) + 1;
      int r = ps.pos[i];
      mps[hs.query(l, r)]++;
    }
  }
  for (int i = 2; i <= pt.sz; i++) {
    padmpt[ht.query(pt.pos[i] - pt.len[i] + 1, pt.pos[i])]++;
    int p = pt.fail[i];
    if (p <= 1) continue;
    if (pt.len[i] <= pt.len[p] * 2) {
      int l = pt.pos[i] - pt.len[i] + 1;
      int r = l + (pt.len[i] - pt.len[p]) - 1;
      mpt[ht.query(l, r)]++;
    }
  }
  for (int i = 2; i <= ps.sz; i++) {
    int p = ps.fail[i];
    if (p <= 1) continue;
    int l = ps.pos[i] - (ps.len[i] - ps.len[p]) + 1;
    int r = ps.pos[i];
    unsigned long long h = hs.query(l, r);
    if (mpt.count(h)) ans -= mpt[h];
    int plen = checkDec(l, r, ps, psr);
    if (plen != -1) {
      unsigned long long pw = hs.query(l, l + plen - 1);
      unsigned long long wt = offset(h, pw, plen);
      if (padmpt.count(pw) && padmpt.count(wt)) {
        ans--;
      }
    }
  }
  for (int i = 2; i <= pt.sz; i++) {
    int p = pt.fail[i];
    if (p <= 1) continue;
    int l = pt.pos[i] - pt.len[i] + 1;
    int r = l + (pt.len[i] - pt.len[p]) - 1;
    unsigned long long h = ht.query(l, r);
    if (mps.count(h)) ans -= mps[h];
    int plen = checkDec(l, r, pt, ptr);
    if (plen != -1) {
      unsigned long long pw = ht.query(l + plen, r);
      unsigned long long tw = offset(pw, h, r - l + 1);
      if (padmps.count(pw) && padmps.count(tw)) {
        ans--;
      }
    }
  }
  for (int i = 2; i <= ps.sz; i++) {
    int p = ps.fail[i];
    if (p <= 1) continue;
    if (ps.len[i] > ps.len[p] * 2) {
      int l = ps.pos[i] - (ps.len[i] - ps.len[p]) + 1;
      int r = ps.pos[i];
      mps[hs.query(l, r)]++;
    }
  }
  for (int i = 2; i <= pt.sz; i++) {
    int p = pt.fail[i];
    if (p <= 1) continue;
    if (pt.len[i] > pt.len[p] * 2) {
      int l = pt.pos[i] - pt.len[i] + 1;
      int r = l + (pt.len[i] - pt.len[p]) - 1;
      mpt[ht.query(l, r)]++;
    }
  }
  for (auto& x : mps) {
    ans += 1ll * x.second * mpt[x.first];
  }
  printf("%I64d\n", ans);
  return 0;
}

```