#include <bits/stdc++.h>
using namespace std;
long long ans;
const int N = 2e5 + 10;
const int S = 26;
const int M = 18;
const long long m1 = 998244353;
const long long m2 = 998244853;
const long long base = 131;
template <typename Type>
inline Type Add1(Type x, Type y) {
  x += y % m1;
  x %= m1;
  return (x + m1) % m1;
}
template <typename Type>
inline Type Dec1(Type x, Type y) {
  x -= y % m1;
  return (x % m1 + m1) % m1;
}
template <typename Type>
inline Type Mul1(Type x, Type y) {
  return ((x * y % m1) + m1) % m1;
}
template <typename Type>
inline Type Add2(Type x, Type y) {
  x += y % m2;
  x %= m2;
  return (x + m2) % m2;
}
template <typename Type>
inline Type Dec2(Type x, Type y) {
  x -= y % m2;
  return (x % m2 + m2) % m2;
}
template <typename Type>
inline Type Mul2(Type x, Type y) {
  return ((x * y % m2) + m2) % m2;
}
struct Hint {
  long long a1, a2;
  friend inline Hint operator+(const Hint &A, const Hint &B) {
    return (Hint){Add1(A.a1, B.a1), Add2(A.a2, B.a2)};
  }
  friend inline Hint operator+(const Hint &A, const long long &B) {
    return (Hint){Add1(A.a1, B), Add2(A.a2, B)};
  }
  friend inline Hint operator-(const Hint &A, const Hint &B) {
    return (Hint){Dec1(A.a1, B.a1), Dec2(A.a2, B.a2)};
  }
  friend inline Hint operator-(const Hint &A, const long long &B) {
    return (Hint){Dec1(A.a1, B), Dec2(A.a2, B)};
  }
  friend inline Hint operator*(const Hint &A, const Hint &B) {
    return (Hint){Mul1(A.a1, B.a1), Mul2(A.a2, B.a2)};
  }
  friend inline Hint operator*(const Hint &A, const long long &B) {
    return (Hint){Mul1(A.a1, B), Mul2(A.a2, B)};
  }
  friend inline bool operator<(const Hint &A, const Hint &B) {
    if (A.a1 != B.a1) return A.a1 < B.a1;
    return A.a2 < B.a2;
  }
};
namespace HASH {
Hint pw[N];
inline void init(int n) {
  pw[0] = (Hint){1, 1};
  for (int i = (1), end_i = (n); i <= end_i; i++) pw[i] = pw[i - 1] * base;
}
inline Hint Hash(Hint *h, int l, int r) {
  return h[r] - (h[l - 1] * pw[r - l + 1]);
}
}  // namespace HASH
using HASH::Hash;
using HASH::pw;
struct PAM {
  int ne[N][S], fail[N], len[N], cnt, las, pos[N], ri[N];
  int s[N], n;
  int f[N][M + 1];
  void init() {
    fail[0] = fail[1] = 1;
    len[cnt = 1] = -1;
    las = 1;
    s[n = 0] = -1;
  }
  inline int getfail(int x) {
    for (; s[n - 1 - len[x]] != s[n]; x = fail[x])
      ;
    return x;
  }
  inline void extend(int c) {
    s[++n] = c;
    int p = getfail(las);
    if (!ne[p][c]) {
      int u = ++cnt, q = getfail(fail[p]);
      len[u] = len[p] + 2;
      fail[u] = ne[q][c];
      ne[p][c] = u;
    }
    las = ne[p][c];
    pos[n] = las;
    ri[pos[n]] = n;
  }
  inline void build(char *s) {
    int n = strlen(s + 1);
    init();
    for (int i = (1), end_i = (n); i <= end_i; i++) extend(s[i] - 'a');
    for (int i = (0), end_i = (cnt); i <= end_i; i++) f[i][0] = fail[i];
    for (int i = (1), end_i = (M); i <= end_i; i++)
      for (int j = (0), end_i = (cnt); j <= end_i; j++)
        f[j][i] = f[f[j][i - 1]][i - 1];
  }
  inline int ask(int r, int l) {
    int x = pos[r];
    if (len[x] <= l) return len[x];
    for (int i = (M), end_i = (0); i >= end_i; i--)
      if (len[f[x][i]] > l) x = f[x][i];
    return len[fail[x]];
  }
  inline bool check(int r, int len) { return ask(r, len) == len; }
};
char a[N], b[N];
PAM la, ra, lb, rb;
Hint ha[N], hb[N];
int n, m;
void init() {
  scanf("%s%s", a + 1, b + 1);
  n = strlen(a + 1);
  m = strlen(b + 1);
  HASH::init(max(n, m) + 2);
  ha[0] = hb[0] = (Hint){0, 0};
  for (int i = (1), end_i = (n); i <= end_i; i++)
    ha[i] = ha[i - 1] * base + (a[i] - 'a' + 1),
    hb[i] = hb[i - 1] * base + (b[i] - 'a' + 1);
  la.build(a);
  lb.build(b);
  reverse(a + 1, a + n + 1);
  reverse(b + 1, b + m + 1);
  ra.build(a);
  rb.build(b);
}
namespace Work1 {
map<Hint, int> ma, mb, wa, wb;
void init() {
  int t;
  for (int i = (2), end_i = (la.cnt); i <= end_i; i++) {
    ma[Hash(ha, la.ri[i] - la.len[i] + 1, la.ri[i])]++;
    if ((t = la.fail[i]) >= 2)
      if (la.len[i] <= (la.len[t] << 1))
        wa[Hash(ha, la.ri[i] - (la.len[i] - la.len[t]) + 1, la.ri[i])]++;
  }
  for (int i = (2), end_i = (lb.cnt); i <= end_i; i++) {
    mb[Hash(hb, lb.ri[i] - lb.len[i] + 1, lb.ri[i])]++;
    if ((t = lb.fail[i]) >= 2)
      if (lb.len[i] <= (lb.len[t] << 1))
        wb[Hash(hb, lb.ri[i] - lb.len[i] + 1, lb.ri[i] - lb.len[t])]++;
  }
}
void work() {
  init();
  int l, r, t, bor, len;
  for (int i = (2), end_i = (la.cnt); i <= end_i; i++)
    if ((t = la.fail[i]) >= 2) {
      l = la.ri[i] - (la.len[i] - la.len[t]) + 1;
      r = la.ri[i];
      len = r - l + 1;
      ans -= wb[Hash(ha, l, r)];
      bor = la.ask(r, len);
      if (len == bor) continue;
      if (ra.check(n - l + 1, len - bor)) {
        if (mb.count(Hash(ha, l, r) * pw[len - bor] + Hash(ha, l, r - bor)))
          ans--;
        continue;
      }
      bor = ra.ask(n - l + 1, len);
      if (la.check(r, len - bor)) {
        if (mb.count(Hash(ha, l, r) * pw[bor] + Hash(ha, l, l + bor - 1)))
          ans--;
        continue;
      }
    }
  for (int i = (2), end_i = (lb.cnt); i <= end_i; i++)
    if ((t = lb.fail[i]) >= 2) {
      l = lb.ri[i] - lb.len[i] + 1;
      r = lb.ri[i] - lb.len[t];
      len = r - l + 1;
      ans -= wa[Hash(hb, l, r)];
      bor = lb.ask(r, len);
      if (len == bor) continue;
      if (rb.check(m - l + 1, len - bor)) {
        if (ma.count(Hash(hb, r - bor + 1, r) * pw[len] + Hash(hb, l, r)))
          ans--;
        continue;
      }
      bor = rb.ask(m - l + 1, len);
      if (lb.check(r, len - bor)) {
        if (ma.count(Hash(hb, l + bor, r) * pw[len] + Hash(hb, l, r))) ans--;
        continue;
      }
    }
}
}  // namespace Work1
namespace Work2 {
int t;
map<Hint, int> fa, fb;
void work() {
  for (int i = (2), end_i = (la.cnt); i <= end_i; i++)
    if ((t = la.fail[i]) >= 2)
      fa[Hash(ha, la.ri[i] - (la.len[i] - la.len[t]) + 1, la.ri[i])]++;
  for (int i = (2), end_i = (lb.cnt); i <= end_i; i++)
    if ((t = lb.fail[i]) >= 2)
      fb[Hash(hb, lb.ri[i] - lb.len[i] + 1, lb.ri[i] - lb.len[t])]++;
  for (auto v : fa) ans += (long long)v.second * fb[v.first];
}
}  // namespace Work2
void work() {
  ans = 1ll * (la.cnt - 1) * (lb.cnt - 1);
  Work1::work();
  Work2::work();
  printf("%lld\n", ans);
}
int main() {
  init();
  work();
  return 0;
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

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;
long long ans;
const int N = 2e5 + 10;
const int S = 26;
const int M = 18;
const long long m1 = 998244353;
const long long m2 = 998244853;
const long long base = 131;
template <typename Type>
inline Type Add1(Type x, Type y) {
  x += y % m1;
  x %= m1;
  return (x + m1) % m1;
}
template <typename Type>
inline Type Dec1(Type x, Type y) {
  x -= y % m1;
  return (x % m1 + m1) % m1;
}
template <typename Type>
inline Type Mul1(Type x, Type y) {
  return ((x * y % m1) + m1) % m1;
}
template <typename Type>
inline Type Add2(Type x, Type y) {
  x += y % m2;
  x %= m2;
  return (x + m2) % m2;
}
template <typename Type>
inline Type Dec2(Type x, Type y) {
  x -= y % m2;
  return (x % m2 + m2) % m2;
}
template <typename Type>
inline Type Mul2(Type x, Type y) {
  return ((x * y % m2) + m2) % m2;
}
struct Hint {
  long long a1, a2;
  friend inline Hint operator+(const Hint &A, const Hint &B) {
    return (Hint){Add1(A.a1, B.a1), Add2(A.a2, B.a2)};
  }
  friend inline Hint operator+(const Hint &A, const long long &B) {
    return (Hint){Add1(A.a1, B), Add2(A.a2, B)};
  }
  friend inline Hint operator-(const Hint &A, const Hint &B) {
    return (Hint){Dec1(A.a1, B.a1), Dec2(A.a2, B.a2)};
  }
  friend inline Hint operator-(const Hint &A, const long long &B) {
    return (Hint){Dec1(A.a1, B), Dec2(A.a2, B)};
  }
  friend inline Hint operator*(const Hint &A, const Hint &B) {
    return (Hint){Mul1(A.a1, B.a1), Mul2(A.a2, B.a2)};
  }
  friend inline Hint operator*(const Hint &A, const long long &B) {
    return (Hint){Mul1(A.a1, B), Mul2(A.a2, B)};
  }
  friend inline bool operator<(const Hint &A, const Hint &B) {
    if (A.a1 != B.a1) return A.a1 < B.a1;
    return A.a2 < B.a2;
  }
};
namespace HASH {
Hint pw[N];
inline void init(int n) {
  pw[0] = (Hint){1, 1};
  for (int i = (1), end_i = (n); i <= end_i; i++) pw[i] = pw[i - 1] * base;
}
inline Hint Hash(Hint *h, int l, int r) {
  return h[r] - (h[l - 1] * pw[r - l + 1]);
}
}  // namespace HASH
using HASH::Hash;
using HASH::pw;
struct PAM {
  int ne[N][S], fail[N], len[N], cnt, las, pos[N], ri[N];
  int s[N], n;
  int f[N][M + 1];
  void init() {
    fail[0] = fail[1] = 1;
    len[cnt = 1] = -1;
    las = 1;
    s[n = 0] = -1;
  }
  inline int getfail(int x) {
    for (; s[n - 1 - len[x]] != s[n]; x = fail[x])
      ;
    return x;
  }
  inline void extend(int c) {
    s[++n] = c;
    int p = getfail(las);
    if (!ne[p][c]) {
      int u = ++cnt, q = getfail(fail[p]);
      len[u] = len[p] + 2;
      fail[u] = ne[q][c];
      ne[p][c] = u;
    }
    las = ne[p][c];
    pos[n] = las;
    ri[pos[n]] = n;
  }
  inline void build(char *s) {
    int n = strlen(s + 1);
    init();
    for (int i = (1), end_i = (n); i <= end_i; i++) extend(s[i] - 'a');
    for (int i = (0), end_i = (cnt); i <= end_i; i++) f[i][0] = fail[i];
    for (int i = (1), end_i = (M); i <= end_i; i++)
      for (int j = (0), end_i = (cnt); j <= end_i; j++)
        f[j][i] = f[f[j][i - 1]][i - 1];
  }
  inline int ask(int r, int l) {
    int x = pos[r];
    if (len[x] <= l) return len[x];
    for (int i = (M), end_i = (0); i >= end_i; i--)
      if (len[f[x][i]] > l) x = f[x][i];
    return len[fail[x]];
  }
  inline bool check(int r, int len) { return ask(r, len) == len; }
};
char a[N], b[N];
PAM la, ra, lb, rb;
Hint ha[N], hb[N];
int n, m;
void init() {
  scanf("%s%s", a + 1, b + 1);
  n = strlen(a + 1);
  m = strlen(b + 1);
  HASH::init(max(n, m) + 2);
  ha[0] = hb[0] = (Hint){0, 0};
  for (int i = (1), end_i = (n); i <= end_i; i++)
    ha[i] = ha[i - 1] * base + (a[i] - 'a' + 1),
    hb[i] = hb[i - 1] * base + (b[i] - 'a' + 1);
  la.build(a);
  lb.build(b);
  reverse(a + 1, a + n + 1);
  reverse(b + 1, b + m + 1);
  ra.build(a);
  rb.build(b);
}
namespace Work1 {
map<Hint, int> ma, mb, wa, wb;
void init() {
  int t;
  for (int i = (2), end_i = (la.cnt); i <= end_i; i++) {
    ma[Hash(ha, la.ri[i] - la.len[i] + 1, la.ri[i])]++;
    if ((t = la.fail[i]) >= 2)
      if (la.len[i] <= (la.len[t] << 1))
        wa[Hash(ha, la.ri[i] - (la.len[i] - la.len[t]) + 1, la.ri[i])]++;
  }
  for (int i = (2), end_i = (lb.cnt); i <= end_i; i++) {
    mb[Hash(hb, lb.ri[i] - lb.len[i] + 1, lb.ri[i])]++;
    if ((t = lb.fail[i]) >= 2)
      if (lb.len[i] <= (lb.len[t] << 1))
        wb[Hash(hb, lb.ri[i] - lb.len[i] + 1, lb.ri[i] - lb.len[t])]++;
  }
}
void work() {
  init();
  int l, r, t, bor, len;
  for (int i = (2), end_i = (la.cnt); i <= end_i; i++)
    if ((t = la.fail[i]) >= 2) {
      l = la.ri[i] - (la.len[i] - la.len[t]) + 1;
      r = la.ri[i];
      len = r - l + 1;
      ans -= wb[Hash(ha, l, r)];
      bor = la.ask(r, len);
      if (len == bor) continue;
      if (ra.check(n - l + 1, len - bor)) {
        if (mb.count(Hash(ha, l, r) * pw[len - bor] + Hash(ha, l, r - bor)))
          ans--;
        continue;
      }
      bor = ra.ask(n - l + 1, len);
      if (la.check(r, len - bor)) {
        if (mb.count(Hash(ha, l, r) * pw[bor] + Hash(ha, l, l + bor - 1)))
          ans--;
        continue;
      }
    }
  for (int i = (2), end_i = (lb.cnt); i <= end_i; i++)
    if ((t = lb.fail[i]) >= 2) {
      l = lb.ri[i] - lb.len[i] + 1;
      r = lb.ri[i] - lb.len[t];
      len = r - l + 1;
      ans -= wa[Hash(hb, l, r)];
      bor = lb.ask(r, len);
      if (len == bor) continue;
      if (rb.check(m - l + 1, len - bor)) {
        if (ma.count(Hash(hb, r - bor + 1, r) * pw[len] + Hash(hb, l, r)))
          ans--;
        continue;
      }
      bor = rb.ask(m - l + 1, len);
      if (lb.check(r, len - bor)) {
        if (ma.count(Hash(hb, l + bor, r) * pw[len] + Hash(hb, l, r))) ans--;
        continue;
      }
    }
}
}  // namespace Work1
namespace Work2 {
int t;
map<Hint, int> fa, fb;
void work() {
  for (int i = (2), end_i = (la.cnt); i <= end_i; i++)
    if ((t = la.fail[i]) >= 2)
      fa[Hash(ha, la.ri[i] - (la.len[i] - la.len[t]) + 1, la.ri[i])]++;
  for (int i = (2), end_i = (lb.cnt); i <= end_i; i++)
    if ((t = lb.fail[i]) >= 2)
      fb[Hash(hb, lb.ri[i] - lb.len[i] + 1, lb.ri[i] - lb.len[t])]++;
  for (auto v : fa) ans += (long long)v.second * fb[v.first];
}
}  // namespace Work2
void work() {
  ans = 1ll * (la.cnt - 1) * (lb.cnt - 1);
  Work1::work();
  Work2::work();
  printf("%lld\n", ans);
}
int main() {
  init();
  work();
  return 0;
}

```