#include <bits/stdc++.h>
char s[200010], t[200010];
const long long P1 = 1000000007, P2 = 998244353, v1 = 6667, v2 = 2333;
long long Pow[2][200010];
struct pam {
  long long cnt, last, fa[200010], len[200010], son[200010][26], nxt[200010],
      S[200010], n, end[200010];
  long long pre[200010][21], pos[200010];
  long long hash[2][200010];
  pam() {
    cnt = 1;
    nxt[0] = 1;
    len[1] = -1;
    S[n = 0] = -1;
  }
  long long getnxt(long long x) {
    while (S[n] != S[n - len[x] - 1]) x = nxt[x];
    return x;
  }
  void add(long long x) {
    S[++n] = x;
    hash[0][n] = (1ll * hash[0][n - 1] * v1 + (x + 1)) % P1;
    hash[1][n] = (1ll * hash[1][n - 1] * v2 + (x + 1)) % P2;
    long long cur = getnxt(last);
    if (!son[cur][x]) {
      end[++cnt] = n;
      nxt[cnt] = son[getnxt(nxt[cur])][x];
      len[son[cur][x] = cnt] = len[cur] + 2;
    }
    last = son[cur][x];
    pos[n] = last;
  }
  void set() {
    for (long long i = 0; i <= cnt; i++) pre[i][0] = nxt[i];
    for (long long j = 1; j <= 20; j++)
      for (long long i = 0; i <= cnt; i++)
        pre[i][j] = pre[pre[i][j - 1]][j - 1];
  }
  std::pair<long long, long long> slice(long long l, long long r) {
    return std::make_pair(
        (hash[0][r] + P1 - (1ll * hash[0][l - 1] * Pow[0][r - l + 1] % P1)) %
            P1,
        (hash[1][r] + P2 - (1ll * hash[1][l - 1] * Pow[1][r - l + 1] % P2)) %
            P2);
  }
  long long palin(long long l, long long r) {
    long long tem = pos[r];
    for (long long i = 20; ~i; --i) {
      if (pre[tem][i] > 1 && len[pre[tem][i]] > r - l + 1) tem = pre[tem][i];
    }
    if (len[tem] > r - l + 1) tem = nxt[tem];
    return len[tem];
  }
  long long cut(long long l, long long r) {
    long long tem = palin(l, r);
    if (tem < r - l + 1 && palin(l, r - tem) + tem == r - l + 1)
      return tem;
    else
      return -1;
  }
} a, b;
long long ans;
std::map<std::pair<long long, long long>, long long> ma, mb;
void getmap(pam &a, std::map<std::pair<long long, long long>, long long> &map,
            long long bb) {
  for (long long i = 2; i <= a.cnt; i++)
    if (a.nxt[i] > 1) {
      if ((bb == 3 && (a.len[a.nxt[i]] << 1) >= a.len[i]) || bb == 0)
        ++map[a.slice(a.end[i] - a.len[i] + a.len[a.nxt[i]] + 1, a.end[i])];
      else if ((bb == 4 && (a.len[a.nxt[i]] << 1) >= a.len[i]) || bb == 1)
        ++map[a.slice(a.end[i] - a.len[i] + 1, a.end[i] - a.len[a.nxt[i]])];
    }
  for (long long i = 2; i <= a.cnt; i++)
    if (bb == 2) ++map[a.slice(a.end[i] - a.len[i] + 1, a.end[i])];
}
std::pair<long long, long long> merge(std::pair<long long, long long> a,
                                      std::pair<long long, long long> b,
                                      long long x) {
  return std::make_pair((1ll * a.first * Pow[0][x] + b.first) % P1,
                        (1ll * a.second * Pow[1][x] + b.second) % P2);
}
void solve(pam &a, std::map<std::pair<long long, long long>, long long> &map,
           bool bb) {
  for (long long i = 2; i <= a.cnt; i++)
    if (a.nxt[i] > 1)
      if (bb) {
        long long r = a.end[i], l = a.end[i] - a.len[i] + a.len[a.nxt[i]] + 1,
                  tem = a.cut(l, r);
        if (~tem && map.count(a.slice(l, r - tem)) &&
            map.count(
                merge(a.slice(l, r), a.slice(l, r - tem), r - l + 1 - tem)))
          --ans;
        else {
          l = a.end[i] - a.len[i] + 1, r = a.end[i] - a.len[a.nxt[i]];
          tem = a.cut(l, r);
          if (~tem) tem = r - l + 1 - tem;
          r = a.end[i], l = a.end[i] - a.len[i] + a.len[a.nxt[i]] + 1;
          if (~tem && map.count(a.slice(l, r - tem)) &&
              map.count(
                  merge(a.slice(l, r), a.slice(l, r - tem), r - l + 1 - tem)))
            --ans;
        }
      } else {
        long long l = a.end[i] - a.len[i] + 1, r = a.end[i] - a.len[a.nxt[i]],
                  tem = a.cut(l, r);
        if (~tem && map.count(a.slice(r - tem + 1, r)) &&
            map.count(merge(a.slice(r - tem + 1, r), a.slice(l, r), r - l + 1)))
          --ans;
        else {
          r = a.end[i], l = a.end[i] - a.len[i] + a.len[a.nxt[i]] + 1;
          tem = a.cut(l, r);
          if (~tem) tem = r - l + 1 - tem;
          l = a.end[i] - a.len[i] + 1, r = a.end[i] - a.len[a.nxt[i]];
          if (~tem && map.count(a.slice(r - tem + 1, r)) &&
              map.count(
                  merge(a.slice(r - tem + 1, r), a.slice(l, r), r - l + 1)))
            --ans;
        }
      }
}
signed main() {
  scanf("%s%s", s + 1, t + 1);
  for (long long i = 1; s[i]; i++) a.add(s[i] - 'a');
  for (long long i = 1; t[i]; i++) b.add(t[i] - 'a');
  Pow[0][0] = Pow[1][0] = 1;
  for (long long i = 1; i <= 200000; i++)
    Pow[0][i] = 1ll * Pow[0][i - 1] * v1 % P1;
  for (long long i = 1; i <= 200000; i++)
    Pow[1][i] = 1ll * Pow[1][i - 1] * v2 % P2;
  ans = 1ll * (a.cnt - 1) * (b.cnt - 1);
  a.set();
  b.set();
  getmap(a, ma, 2);
  getmap(b, mb, 2);
  solve(a, mb, 1);
  solve(b, ma, 0);
  ma.clear();
  mb.clear();
  getmap(a, ma, 0);
  getmap(b, mb, 4);
  for (auto it = ma.begin(); it != ma.end(); ++it)
    ans -= 1ll * it->second * mb[it->first];
  ma.clear();
  mb.clear();
  getmap(a, ma, 3);
  getmap(b, mb, 1);
  for (auto it = ma.begin(); it != ma.end(); ++it)
    ans -= 1ll * it->second * mb[it->first];
  ma.clear();
  mb.clear();
  getmap(a, ma, 0);
  getmap(b, mb, 1);
  for (auto it = ma.begin(); it != ma.end(); ++it)
    ans += 1ll * it->second * mb[it->first];
  printf("%lld\n", ans);
}

### Prompt

Generate 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>
char s[200010], t[200010];
const long long P1 = 1000000007, P2 = 998244353, v1 = 6667, v2 = 2333;
long long Pow[2][200010];
struct pam {
  long long cnt, last, fa[200010], len[200010], son[200010][26], nxt[200010],
      S[200010], n, end[200010];
  long long pre[200010][21], pos[200010];
  long long hash[2][200010];
  pam() {
    cnt = 1;
    nxt[0] = 1;
    len[1] = -1;
    S[n = 0] = -1;
  }
  long long getnxt(long long x) {
    while (S[n] != S[n - len[x] - 1]) x = nxt[x];
    return x;
  }
  void add(long long x) {
    S[++n] = x;
    hash[0][n] = (1ll * hash[0][n - 1] * v1 + (x + 1)) % P1;
    hash[1][n] = (1ll * hash[1][n - 1] * v2 + (x + 1)) % P2;
    long long cur = getnxt(last);
    if (!son[cur][x]) {
      end[++cnt] = n;
      nxt[cnt] = son[getnxt(nxt[cur])][x];
      len[son[cur][x] = cnt] = len[cur] + 2;
    }
    last = son[cur][x];
    pos[n] = last;
  }
  void set() {
    for (long long i = 0; i <= cnt; i++) pre[i][0] = nxt[i];
    for (long long j = 1; j <= 20; j++)
      for (long long i = 0; i <= cnt; i++)
        pre[i][j] = pre[pre[i][j - 1]][j - 1];
  }
  std::pair<long long, long long> slice(long long l, long long r) {
    return std::make_pair(
        (hash[0][r] + P1 - (1ll * hash[0][l - 1] * Pow[0][r - l + 1] % P1)) %
            P1,
        (hash[1][r] + P2 - (1ll * hash[1][l - 1] * Pow[1][r - l + 1] % P2)) %
            P2);
  }
  long long palin(long long l, long long r) {
    long long tem = pos[r];
    for (long long i = 20; ~i; --i) {
      if (pre[tem][i] > 1 && len[pre[tem][i]] > r - l + 1) tem = pre[tem][i];
    }
    if (len[tem] > r - l + 1) tem = nxt[tem];
    return len[tem];
  }
  long long cut(long long l, long long r) {
    long long tem = palin(l, r);
    if (tem < r - l + 1 && palin(l, r - tem) + tem == r - l + 1)
      return tem;
    else
      return -1;
  }
} a, b;
long long ans;
std::map<std::pair<long long, long long>, long long> ma, mb;
void getmap(pam &a, std::map<std::pair<long long, long long>, long long> &map,
            long long bb) {
  for (long long i = 2; i <= a.cnt; i++)
    if (a.nxt[i] > 1) {
      if ((bb == 3 && (a.len[a.nxt[i]] << 1) >= a.len[i]) || bb == 0)
        ++map[a.slice(a.end[i] - a.len[i] + a.len[a.nxt[i]] + 1, a.end[i])];
      else if ((bb == 4 && (a.len[a.nxt[i]] << 1) >= a.len[i]) || bb == 1)
        ++map[a.slice(a.end[i] - a.len[i] + 1, a.end[i] - a.len[a.nxt[i]])];
    }
  for (long long i = 2; i <= a.cnt; i++)
    if (bb == 2) ++map[a.slice(a.end[i] - a.len[i] + 1, a.end[i])];
}
std::pair<long long, long long> merge(std::pair<long long, long long> a,
                                      std::pair<long long, long long> b,
                                      long long x) {
  return std::make_pair((1ll * a.first * Pow[0][x] + b.first) % P1,
                        (1ll * a.second * Pow[1][x] + b.second) % P2);
}
void solve(pam &a, std::map<std::pair<long long, long long>, long long> &map,
           bool bb) {
  for (long long i = 2; i <= a.cnt; i++)
    if (a.nxt[i] > 1)
      if (bb) {
        long long r = a.end[i], l = a.end[i] - a.len[i] + a.len[a.nxt[i]] + 1,
                  tem = a.cut(l, r);
        if (~tem && map.count(a.slice(l, r - tem)) &&
            map.count(
                merge(a.slice(l, r), a.slice(l, r - tem), r - l + 1 - tem)))
          --ans;
        else {
          l = a.end[i] - a.len[i] + 1, r = a.end[i] - a.len[a.nxt[i]];
          tem = a.cut(l, r);
          if (~tem) tem = r - l + 1 - tem;
          r = a.end[i], l = a.end[i] - a.len[i] + a.len[a.nxt[i]] + 1;
          if (~tem && map.count(a.slice(l, r - tem)) &&
              map.count(
                  merge(a.slice(l, r), a.slice(l, r - tem), r - l + 1 - tem)))
            --ans;
        }
      } else {
        long long l = a.end[i] - a.len[i] + 1, r = a.end[i] - a.len[a.nxt[i]],
                  tem = a.cut(l, r);
        if (~tem && map.count(a.slice(r - tem + 1, r)) &&
            map.count(merge(a.slice(r - tem + 1, r), a.slice(l, r), r - l + 1)))
          --ans;
        else {
          r = a.end[i], l = a.end[i] - a.len[i] + a.len[a.nxt[i]] + 1;
          tem = a.cut(l, r);
          if (~tem) tem = r - l + 1 - tem;
          l = a.end[i] - a.len[i] + 1, r = a.end[i] - a.len[a.nxt[i]];
          if (~tem && map.count(a.slice(r - tem + 1, r)) &&
              map.count(
                  merge(a.slice(r - tem + 1, r), a.slice(l, r), r - l + 1)))
            --ans;
        }
      }
}
signed main() {
  scanf("%s%s", s + 1, t + 1);
  for (long long i = 1; s[i]; i++) a.add(s[i] - 'a');
  for (long long i = 1; t[i]; i++) b.add(t[i] - 'a');
  Pow[0][0] = Pow[1][0] = 1;
  for (long long i = 1; i <= 200000; i++)
    Pow[0][i] = 1ll * Pow[0][i - 1] * v1 % P1;
  for (long long i = 1; i <= 200000; i++)
    Pow[1][i] = 1ll * Pow[1][i - 1] * v2 % P2;
  ans = 1ll * (a.cnt - 1) * (b.cnt - 1);
  a.set();
  b.set();
  getmap(a, ma, 2);
  getmap(b, mb, 2);
  solve(a, mb, 1);
  solve(b, ma, 0);
  ma.clear();
  mb.clear();
  getmap(a, ma, 0);
  getmap(b, mb, 4);
  for (auto it = ma.begin(); it != ma.end(); ++it)
    ans -= 1ll * it->second * mb[it->first];
  ma.clear();
  mb.clear();
  getmap(a, ma, 3);
  getmap(b, mb, 1);
  for (auto it = ma.begin(); it != ma.end(); ++it)
    ans -= 1ll * it->second * mb[it->first];
  ma.clear();
  mb.clear();
  getmap(a, ma, 0);
  getmap(b, mb, 1);
  for (auto it = ma.begin(); it != ma.end(); ++it)
    ans += 1ll * it->second * mb[it->first];
  printf("%lld\n", ans);
}

```