#include <bits/stdc++.h>
using namespace std;
int get() {
  char ch;
  while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-')
    ;
  if (ch == '-') {
    int s = 0;
    while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
    return -s;
  }
  int s = ch - '0';
  while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
  return s;
}
const int N = 2e5 + 5;
const int M = 2e6 + 5;
const int Mod1 = 971733731;
const int Mod2 = 1e9 + 9;
const int P = 127;
long long quickmi(long long x, long long tim, long long mo) {
  long long ret = 1;
  for (; tim; tim /= 2, x = x * x % mo)
    if (tim & 1) ret = ret * x % mo;
  return ret;
}
struct haxi {
  long long v1, v2;
  haxi(const long long v1_ = 0, const long long v2_ = 0) {
    v1 = v1_;
    v2 = v2_;
  }
  friend bool operator<(haxi a, haxi b) {
    return a.v1 != b.v1 ? a.v1 < b.v1 : a.v2 < b.v2;
  }
};
haxi operator+(haxi a, haxi b) {
  return haxi((a.v1 + b.v1) % Mod1, (a.v2 + b.v2) % Mod2);
}
haxi operator-(haxi a, haxi b) {
  return haxi((a.v1 + Mod1 - b.v1) % Mod1, (a.v2 + Mod2 - b.v2) % Mod2);
}
haxi operator*(haxi a, haxi b) {
  return haxi(a.v1 * b.v1 % Mod1, a.v2 * b.v2 % Mod2);
}
haxi operator+(haxi a, int v) {
  return haxi((a.v1 + v) % Mod1, (a.v2 + v) % Mod2);
}
haxi operator*(haxi a, int v) { return haxi(a.v1 * v % Mod1, a.v2 * v % Mod2); }
int n, m;
char s1[N], s2[N];
struct palindrome_tree {
  struct node {
    int son[26];
    int len, fa, pos, to;
  } tree[N];
  int tot, n;
  char a[N];
  int fa[N][20];
  int lim;
  void init() {
    tot = 2;
    tree[1].len = -1;
    tree[2].len = 0;
    tree[2].fa = 1;
  }
  int key1[N], key2[N];
  void build(char *s, int len) {
    int now = 2;
    n = len;
    for (int i = 1; i <= len; i++) {
      a[i] = s[i];
      int c = s[i] - 'a';
      for (; now && s[i - tree[now].len - 1] != s[i]; now = tree[now].fa)
        ;
      if (!tree[now].son[c]) {
        int x = tree[now].son[c] = ++tot;
        tree[x].pos = i;
        tree[x].len = tree[now].len + 2;
        now = tree[now].fa;
        for (; now && s[i - tree[now].len - 1] != s[i]; now = tree[now].fa)
          ;
        if (tree[now].son[c])
          tree[x].fa = tree[now].son[c];
        else
          tree[x].fa = 2;
        int y = tree[x].fa;
        if (tree[x].len - tree[y].len == tree[y].len - tree[tree[y].fa].len)
          tree[x].to = tree[y].to;
        else
          tree[x].to = y;
        now = x;
      } else
        now = tree[now].son[c];
      key1[i] = now;
    }
    now = 2;
    for (int i = len; i >= 1; i--) {
      int c = s[i] - 'a';
      for (; now && s[i + tree[now].len + 1] != s[i]; now = tree[now].fa)
        ;
      now = tree[now].son[c];
      key2[i] = now;
    }
    lim = log(tot) / log(2);
    for (int i = 1; i <= tot; i++) {
      fa[i][0] = tree[i].fa;
      for (int j = 1; j <= lim; j++) fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
  }
  int jump(int x, int len) {
    if (tree[x].len <= len) return x;
    for (int i = lim; i >= 0; i--)
      if (tree[fa[x][i]].len > len) x = fa[x][i];
    return fa[x][0];
  }
  int double_pal(int l, int r) {
    int x = jump(key2[l], r - l), y = jump(key1[r], r - l);
    int ret = 0;
    if (x > 2)
      ret = tree[jump(key1[r], r - l + 1 - tree[x].len)].len ==
                    r - l + 1 - tree[x].len
                ? tree[x].len
                : 0;
    if (y > 2 && !ret)
      ret = tree[jump(key2[l], r - l + 1 - tree[y].len)].len ==
                    r - l + 1 - tree[y].len
                ? r - l + 1 - tree[y].len
                : 0;
    return ret;
  }
} PA, PB;
haxi mi[M], ny[M];
haxi pre1[N], pre2[N];
map<haxi, int> cnt;
haxi getsec1(int l, int r) { return pre1[r] - pre1[l - 1] * mi[r - l + 1]; }
haxi getsec2(int l, int r) { return pre2[r] - pre2[l - 1] * mi[r - l + 1]; }
map<haxi, int> cnta, cntb;
haxi A[N], B[N];
map<haxi, int> ida, idb;
int main() {
  scanf("%s", s1 + 1);
  scanf("%s", s2 + 1);
  n = strlen(s1 + 1);
  m = strlen(s2 + 1);
  PA.init();
  PA.build(s1, n);
  PB.init();
  PB.build(s2, m);
  mi[0] = haxi(1, 1);
  for (int i = 1; i <= 1e6; i++) mi[i] = mi[i - 1] * P;
  ny[0] = haxi(1, 1);
  ny[1] = haxi(quickmi(P, Mod1 - 2, Mod1), quickmi(P, Mod2 - 2, Mod2));
  for (int i = 2; i <= 1e6; i++) ny[i] = ny[i - 1] * ny[1];
  for (int i = 1; i <= n; i++) pre1[i] = pre1[i - 1] * P + s1[i];
  for (int i = 1; i <= m; i++) pre2[i] = pre2[i - 1] * P + s2[i];
  long long ans = 1ll * (PA.tot - 2) * (PB.tot - 2);
  for (int x = 3; x <= PB.tot; x++) {
    int wx = PB.tree[x].pos;
    int lenx = PB.tree[x].len;
    haxi hax = getsec2(wx - lenx + 1, wx);
    cntb[B[x] = hax]++;
    idb[hax] = x;
    if (PB.tree[x].fa > 2) {
      int y = PB.tree[x].fa;
      int wy = PB.tree[y].pos;
      int leny = PB.tree[y].len;
      haxi hay = getsec2(wy - leny + 1, wy);
      haxi ha = (hax - hay) * ny[leny];
      cnt[ha]++;
    }
  }
  for (int x = 3; x <= PA.tot; x++) {
    int wx = PA.tree[x].pos;
    int lenx = PA.tree[x].len;
    haxi hax = getsec1(wx - lenx + 1, wx);
    cnta[A[x] = hax]++;
    ida[hax] = x;
    if (PA.tree[x].fa > 2) {
      int y = PA.tree[x].fa;
      int wy = PA.tree[y].pos;
      int leny = PA.tree[y].len;
      haxi hay = getsec1(wy - leny + 1, wy);
      haxi ha = hax - hay * mi[lenx - leny];
      ans = ans - cnt[ha];
    }
  }
  for (int x = 3; x <= PA.tot; x++) {
    if (PA.tree[x].fa > 2) {
      int y = PA.tree[x].fa;
      int l = PA.tree[x].pos - PA.tree[x].len + PA.tree[y].len + 1,
          r = PA.tree[x].pos;
      int d = PA.double_pal(l, r);
      if (d) {
        haxi h1 = getsec1(l, r), h2 = getsec1(l, l + d - 1);
        h1 = h1 * mi[d] + h2;
        int p = idb[h1];
        if (PB.tree[PB.tree[p].fa].len > d) ans = ans - cntb[h1];
      }
    }
  }
  for (int x = 3; x <= PB.tot; x++) {
    if (PB.tree[x].fa > 2) {
      int y = PB.tree[x].fa;
      int l = PB.tree[x].pos - PB.tree[x].len + 1,
          r = PB.tree[x].pos - PB.tree[y].len;
      int d = PB.double_pal(l, r);
      if (d) {
        haxi h1 = getsec2(l, r), h2 = getsec2(l + d, r);
        h1 = h2 * mi[r - l + 1] + h1;
        int p = ida[h1];
        if (PA.tree[PA.tree[p].fa].len > r - l + 1 - d) ans = ans - cnta[h1];
      }
    }
  }
  cout << ans << endl;
  return 0;
}

### Prompt

In CPP, your task is to solve 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;
int get() {
  char ch;
  while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-')
    ;
  if (ch == '-') {
    int s = 0;
    while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
    return -s;
  }
  int s = ch - '0';
  while (ch = getchar(), ch >= '0' && ch <= '9') s = s * 10 + ch - '0';
  return s;
}
const int N = 2e5 + 5;
const int M = 2e6 + 5;
const int Mod1 = 971733731;
const int Mod2 = 1e9 + 9;
const int P = 127;
long long quickmi(long long x, long long tim, long long mo) {
  long long ret = 1;
  for (; tim; tim /= 2, x = x * x % mo)
    if (tim & 1) ret = ret * x % mo;
  return ret;
}
struct haxi {
  long long v1, v2;
  haxi(const long long v1_ = 0, const long long v2_ = 0) {
    v1 = v1_;
    v2 = v2_;
  }
  friend bool operator<(haxi a, haxi b) {
    return a.v1 != b.v1 ? a.v1 < b.v1 : a.v2 < b.v2;
  }
};
haxi operator+(haxi a, haxi b) {
  return haxi((a.v1 + b.v1) % Mod1, (a.v2 + b.v2) % Mod2);
}
haxi operator-(haxi a, haxi b) {
  return haxi((a.v1 + Mod1 - b.v1) % Mod1, (a.v2 + Mod2 - b.v2) % Mod2);
}
haxi operator*(haxi a, haxi b) {
  return haxi(a.v1 * b.v1 % Mod1, a.v2 * b.v2 % Mod2);
}
haxi operator+(haxi a, int v) {
  return haxi((a.v1 + v) % Mod1, (a.v2 + v) % Mod2);
}
haxi operator*(haxi a, int v) { return haxi(a.v1 * v % Mod1, a.v2 * v % Mod2); }
int n, m;
char s1[N], s2[N];
struct palindrome_tree {
  struct node {
    int son[26];
    int len, fa, pos, to;
  } tree[N];
  int tot, n;
  char a[N];
  int fa[N][20];
  int lim;
  void init() {
    tot = 2;
    tree[1].len = -1;
    tree[2].len = 0;
    tree[2].fa = 1;
  }
  int key1[N], key2[N];
  void build(char *s, int len) {
    int now = 2;
    n = len;
    for (int i = 1; i <= len; i++) {
      a[i] = s[i];
      int c = s[i] - 'a';
      for (; now && s[i - tree[now].len - 1] != s[i]; now = tree[now].fa)
        ;
      if (!tree[now].son[c]) {
        int x = tree[now].son[c] = ++tot;
        tree[x].pos = i;
        tree[x].len = tree[now].len + 2;
        now = tree[now].fa;
        for (; now && s[i - tree[now].len - 1] != s[i]; now = tree[now].fa)
          ;
        if (tree[now].son[c])
          tree[x].fa = tree[now].son[c];
        else
          tree[x].fa = 2;
        int y = tree[x].fa;
        if (tree[x].len - tree[y].len == tree[y].len - tree[tree[y].fa].len)
          tree[x].to = tree[y].to;
        else
          tree[x].to = y;
        now = x;
      } else
        now = tree[now].son[c];
      key1[i] = now;
    }
    now = 2;
    for (int i = len; i >= 1; i--) {
      int c = s[i] - 'a';
      for (; now && s[i + tree[now].len + 1] != s[i]; now = tree[now].fa)
        ;
      now = tree[now].son[c];
      key2[i] = now;
    }
    lim = log(tot) / log(2);
    for (int i = 1; i <= tot; i++) {
      fa[i][0] = tree[i].fa;
      for (int j = 1; j <= lim; j++) fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
  }
  int jump(int x, int len) {
    if (tree[x].len <= len) return x;
    for (int i = lim; i >= 0; i--)
      if (tree[fa[x][i]].len > len) x = fa[x][i];
    return fa[x][0];
  }
  int double_pal(int l, int r) {
    int x = jump(key2[l], r - l), y = jump(key1[r], r - l);
    int ret = 0;
    if (x > 2)
      ret = tree[jump(key1[r], r - l + 1 - tree[x].len)].len ==
                    r - l + 1 - tree[x].len
                ? tree[x].len
                : 0;
    if (y > 2 && !ret)
      ret = tree[jump(key2[l], r - l + 1 - tree[y].len)].len ==
                    r - l + 1 - tree[y].len
                ? r - l + 1 - tree[y].len
                : 0;
    return ret;
  }
} PA, PB;
haxi mi[M], ny[M];
haxi pre1[N], pre2[N];
map<haxi, int> cnt;
haxi getsec1(int l, int r) { return pre1[r] - pre1[l - 1] * mi[r - l + 1]; }
haxi getsec2(int l, int r) { return pre2[r] - pre2[l - 1] * mi[r - l + 1]; }
map<haxi, int> cnta, cntb;
haxi A[N], B[N];
map<haxi, int> ida, idb;
int main() {
  scanf("%s", s1 + 1);
  scanf("%s", s2 + 1);
  n = strlen(s1 + 1);
  m = strlen(s2 + 1);
  PA.init();
  PA.build(s1, n);
  PB.init();
  PB.build(s2, m);
  mi[0] = haxi(1, 1);
  for (int i = 1; i <= 1e6; i++) mi[i] = mi[i - 1] * P;
  ny[0] = haxi(1, 1);
  ny[1] = haxi(quickmi(P, Mod1 - 2, Mod1), quickmi(P, Mod2 - 2, Mod2));
  for (int i = 2; i <= 1e6; i++) ny[i] = ny[i - 1] * ny[1];
  for (int i = 1; i <= n; i++) pre1[i] = pre1[i - 1] * P + s1[i];
  for (int i = 1; i <= m; i++) pre2[i] = pre2[i - 1] * P + s2[i];
  long long ans = 1ll * (PA.tot - 2) * (PB.tot - 2);
  for (int x = 3; x <= PB.tot; x++) {
    int wx = PB.tree[x].pos;
    int lenx = PB.tree[x].len;
    haxi hax = getsec2(wx - lenx + 1, wx);
    cntb[B[x] = hax]++;
    idb[hax] = x;
    if (PB.tree[x].fa > 2) {
      int y = PB.tree[x].fa;
      int wy = PB.tree[y].pos;
      int leny = PB.tree[y].len;
      haxi hay = getsec2(wy - leny + 1, wy);
      haxi ha = (hax - hay) * ny[leny];
      cnt[ha]++;
    }
  }
  for (int x = 3; x <= PA.tot; x++) {
    int wx = PA.tree[x].pos;
    int lenx = PA.tree[x].len;
    haxi hax = getsec1(wx - lenx + 1, wx);
    cnta[A[x] = hax]++;
    ida[hax] = x;
    if (PA.tree[x].fa > 2) {
      int y = PA.tree[x].fa;
      int wy = PA.tree[y].pos;
      int leny = PA.tree[y].len;
      haxi hay = getsec1(wy - leny + 1, wy);
      haxi ha = hax - hay * mi[lenx - leny];
      ans = ans - cnt[ha];
    }
  }
  for (int x = 3; x <= PA.tot; x++) {
    if (PA.tree[x].fa > 2) {
      int y = PA.tree[x].fa;
      int l = PA.tree[x].pos - PA.tree[x].len + PA.tree[y].len + 1,
          r = PA.tree[x].pos;
      int d = PA.double_pal(l, r);
      if (d) {
        haxi h1 = getsec1(l, r), h2 = getsec1(l, l + d - 1);
        h1 = h1 * mi[d] + h2;
        int p = idb[h1];
        if (PB.tree[PB.tree[p].fa].len > d) ans = ans - cntb[h1];
      }
    }
  }
  for (int x = 3; x <= PB.tot; x++) {
    if (PB.tree[x].fa > 2) {
      int y = PB.tree[x].fa;
      int l = PB.tree[x].pos - PB.tree[x].len + 1,
          r = PB.tree[x].pos - PB.tree[y].len;
      int d = PB.double_pal(l, r);
      if (d) {
        haxi h1 = getsec2(l, r), h2 = getsec2(l + d, r);
        h1 = h2 * mi[r - l + 1] + h1;
        int p = ida[h1];
        if (PA.tree[PA.tree[p].fa].len > r - l + 1 - d) ans = ans - cnta[h1];
      }
    }
  }
  cout << ans << endl;
  return 0;
}

```