#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
const int LOG = 17;
const int base = 31;
const int mod[2] = {(int)1e9 + 7, (int)1e9 + 9};
struct Pal {
  char s[N];
  int nxt[N][26], fail[N], last[N], anc[N][LOG + 1], len[N], pos[N], cnt;
  Pal() {
    last[0] = 1;
    cnt = 1;
    fail[0] = fail[1] = 1;
    len[1] = -1;
  }
  void add(int n) {
    int c = s[n] - 'a';
    int v = last[n - 1];
    while (s[n - len[v] - 1] != s[n]) v = fail[v];
    if (!nxt[v][c]) {
      int now = ++cnt, k = fail[v];
      pos[now] = n;
      len[now] = len[v] + 2;
      while (s[n - len[k] - 1] != s[n]) k = fail[k];
      fail[now] = nxt[k][c], nxt[v][c] = now;
    }
    last[n] = nxt[v][c];
  }
  void build() {
    int n = strlen(s + 1);
    for (int i = 1; i <= n; ++i) add(i);
    for (int i = 0; i <= cnt; ++i) anc[i][0] = fail[i];
    for (int i = 0; i <= cnt; ++i)
      for (int j = 1; j <= LOG; ++j) anc[i][j] = anc[anc[i][j - 1]][j - 1];
  }
  bool czypal(int l, int r) {
    int L = r - l + 1;
    int v = last[r];
    for (int i = LOG; 0 <= i; --i)
      if (len[anc[v][i]] >= L) v = anc[v][i];
    return len[v] == L;
  }
  int qw(int l, int r) {
    int L = r - l + 1;
    int v = last[r];
    if (len[v] <= L) return len[v];
    for (int i = LOG; 0 <= i; --i)
      if (len[anc[v][i]] > L) v = anc[v][i];
    return len[anc[v][0]];
  }
} A, B, AR, BR;
char a[N], b[N];
int P[N][2];
int HA[N][2];
int HB[N][2];
int AA(int l, int r, int j) {
  return (HA[r][j] - 1LL * HA[l - 1][j] * P[r - l + 1][j] % mod[j] + mod[j]) %
         mod[j];
}
int BB(int l, int r, int j) {
  return (HB[r][j] - 1LL * HB[l - 1][j] * P[r - l + 1][j] % mod[j] + mod[j]) %
         mod[j];
}
long long Ahasz(int l, int r) {
  return 1LL * AA(l, r, 0) * mod[0] + AA(l, r, 1);
}
long long Bhasz(int l, int r) {
  return 1LL * BB(l, r, 0) * mod[0] + BB(l, r, 1);
}
long long Atwo(int l1, int r1, int l2, int r2) {
  int x = (AA(l2, r2, 0) + 1LL * AA(l1, r1, 0) * P[r2 - l2 + 1][0] % mod[0]) %
          mod[0];
  int y = (AA(l2, r2, 1) + 1LL * AA(l1, r1, 1) * P[r2 - l2 + 1][1] % mod[1]) %
          mod[1];
  return 1LL * x * mod[0] + y;
}
long long Btwo(int l1, int r1, int l2, int r2) {
  int x = (BB(l2, r2, 0) + 1LL * BB(l1, r1, 0) * P[r2 - l2 + 1][0] % mod[0]) %
          mod[0];
  int y = (BB(l2, r2, 1) + 1LL * BB(l1, r1, 1) * P[r2 - l2 + 1][1] % mod[1]) %
          mod[1];
  return 1LL * x * mod[0] + y;
}
unordered_map<long long, int> PA, PB, GA, GB;
int main() {
  scanf("%s%s", a + 1, b + 1);
  int n = strlen(a + 1), m = strlen(b + 1);
  P[0][0] = P[0][1] = 1;
  for (int i = 1; i <= N - 1; ++i)
    for (int j = 0; j <= 1; ++j) P[i][j] = 1LL * P[i - 1][j] * base % mod[j];
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= 1; ++j)
      HA[i][j] = (1LL * HA[i - 1][j] * base + a[i]) % mod[j];
  for (int i = 1; i <= m; ++i)
    for (int j = 0; j <= 1; ++j)
      HB[i][j] = (1LL * HB[i - 1][j] * base + b[i]) % mod[j];
  for (int i = 1; i <= n; ++i) A.s[i] = AR.s[n - i + 1] = a[i];
  for (int i = 1; i <= m; ++i) B.s[i] = BR.s[m - i + 1] = b[i];
  A.build();
  B.build();
  AR.build();
  BR.build();
  long long answer = 1LL * (A.cnt - 1) * (B.cnt - 1);
  for (int i = 2; i <= A.cnt; ++i) {
    int p = A.fail[i];
    PA[Ahasz(A.pos[i] - A.len[i] + 1, A.pos[i])]++;
    if (!p) continue;
    if (2 * A.len[p] >= A.len[i])
      GA[Ahasz(A.pos[i] - (A.len[i] - A.len[p]) + 1, A.pos[i])]++;
  }
  for (int i = 2; i <= B.cnt; ++i) {
    int p = B.fail[i];
    PB[Bhasz(B.pos[i] - B.len[i] + 1, B.pos[i])]++;
    if (!p) continue;
    if (2 * A.len[p] >= B.len[i])
      GB[Bhasz(B.pos[i] - B.len[i] + 1, B.pos[i] - B.len[p])]++;
  }
  for (int i = 2; i <= A.cnt; ++i) {
    int p = A.fail[i];
    if (!p) continue;
    int l = A.pos[i] - (A.len[i] - A.len[p]) + 1, r = A.pos[i];
    if (GB.count(Ahasz(l, r))) answer -= GB[Ahasz(l, r)];
    int dlugosc = A.qw(l, r);
    if (dlugosc == r - l + 1 || dlugosc <= 0) continue;
    int mid = r - dlugosc + 1;
    if (A.czypal(l, mid - 1) == true) {
      long long H1 = Ahasz(l, mid - 1);
      long long H2 = Atwo(l, r, l, mid - 1);
      if (PB.count(H1) && PB.count(H2)) answer--;
      continue;
    }
    dlugosc = AR.qw(n - r + 1, n - l + 1);
    if (dlugosc <= 0) continue;
    mid = l + dlugosc - 1;
    if (A.czypal(mid + 1, r) == true) {
      long long H1 = Ahasz(l, mid);
      long long H2 = Atwo(l, r, l, mid);
      if (PB.count(H1) && PB.count(H2)) answer--;
    }
  }
  for (int i = 2; i <= B.cnt; ++i) {
    int p = B.fail[i];
    if (!p) continue;
    int l = B.pos[i] - B.len[i] + 1, r = B.pos[i] - B.len[p];
    if (GA.count(Bhasz(l, r))) answer -= GA[Bhasz(l, r)];
    int dlugosc = B.qw(l, r);
    if (dlugosc == r - l + 1 || dlugosc <= 0) continue;
    int mid = r - dlugosc + 1;
    if (B.czypal(l, mid - 1) == true) {
      long long H1 = Bhasz(mid, r);
      long long H2 = Btwo(mid, r, l, r);
      if (PA.count(H1) && PA.count(H2)) answer--;
      continue;
    }
    dlugosc = BR.qw(m - r + 1, m - l + 1);
    if (dlugosc <= 0) continue;
    mid = l + dlugosc - 1;
    if (B.czypal(mid + 1, r) == true) {
      long long H1 = Bhasz(mid + 1, r);
      long long H2 = Btwo(mid + 1, r, l, r);
      if (PA.count(H1) && PA.count(H2)) answer--;
    }
  }
  for (int i = 2; i <= A.cnt; ++i) {
    int p = A.fail[i];
    if (!p) continue;
    if (2 * A.len[p] < A.len[i])
      GA[Ahasz(A.pos[i] - (A.len[i] - A.len[p]) + 1, A.pos[i])]++;
  }
  for (int i = 2; i <= B.cnt; ++i) {
    int p = B.fail[i];
    if (!p) continue;
    if (2 * B.len[p] < B.len[i])
      GB[Bhasz(B.pos[i] - B.len[i] + 1, B.pos[i] - B.len[p])]++;
  }
  for (auto it : GA) answer += 1LL * it.second * GB[it.first];
  printf("%lld\n", answer);
  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;
const int N = 2e5 + 100;
const int LOG = 17;
const int base = 31;
const int mod[2] = {(int)1e9 + 7, (int)1e9 + 9};
struct Pal {
  char s[N];
  int nxt[N][26], fail[N], last[N], anc[N][LOG + 1], len[N], pos[N], cnt;
  Pal() {
    last[0] = 1;
    cnt = 1;
    fail[0] = fail[1] = 1;
    len[1] = -1;
  }
  void add(int n) {
    int c = s[n] - 'a';
    int v = last[n - 1];
    while (s[n - len[v] - 1] != s[n]) v = fail[v];
    if (!nxt[v][c]) {
      int now = ++cnt, k = fail[v];
      pos[now] = n;
      len[now] = len[v] + 2;
      while (s[n - len[k] - 1] != s[n]) k = fail[k];
      fail[now] = nxt[k][c], nxt[v][c] = now;
    }
    last[n] = nxt[v][c];
  }
  void build() {
    int n = strlen(s + 1);
    for (int i = 1; i <= n; ++i) add(i);
    for (int i = 0; i <= cnt; ++i) anc[i][0] = fail[i];
    for (int i = 0; i <= cnt; ++i)
      for (int j = 1; j <= LOG; ++j) anc[i][j] = anc[anc[i][j - 1]][j - 1];
  }
  bool czypal(int l, int r) {
    int L = r - l + 1;
    int v = last[r];
    for (int i = LOG; 0 <= i; --i)
      if (len[anc[v][i]] >= L) v = anc[v][i];
    return len[v] == L;
  }
  int qw(int l, int r) {
    int L = r - l + 1;
    int v = last[r];
    if (len[v] <= L) return len[v];
    for (int i = LOG; 0 <= i; --i)
      if (len[anc[v][i]] > L) v = anc[v][i];
    return len[anc[v][0]];
  }
} A, B, AR, BR;
char a[N], b[N];
int P[N][2];
int HA[N][2];
int HB[N][2];
int AA(int l, int r, int j) {
  return (HA[r][j] - 1LL * HA[l - 1][j] * P[r - l + 1][j] % mod[j] + mod[j]) %
         mod[j];
}
int BB(int l, int r, int j) {
  return (HB[r][j] - 1LL * HB[l - 1][j] * P[r - l + 1][j] % mod[j] + mod[j]) %
         mod[j];
}
long long Ahasz(int l, int r) {
  return 1LL * AA(l, r, 0) * mod[0] + AA(l, r, 1);
}
long long Bhasz(int l, int r) {
  return 1LL * BB(l, r, 0) * mod[0] + BB(l, r, 1);
}
long long Atwo(int l1, int r1, int l2, int r2) {
  int x = (AA(l2, r2, 0) + 1LL * AA(l1, r1, 0) * P[r2 - l2 + 1][0] % mod[0]) %
          mod[0];
  int y = (AA(l2, r2, 1) + 1LL * AA(l1, r1, 1) * P[r2 - l2 + 1][1] % mod[1]) %
          mod[1];
  return 1LL * x * mod[0] + y;
}
long long Btwo(int l1, int r1, int l2, int r2) {
  int x = (BB(l2, r2, 0) + 1LL * BB(l1, r1, 0) * P[r2 - l2 + 1][0] % mod[0]) %
          mod[0];
  int y = (BB(l2, r2, 1) + 1LL * BB(l1, r1, 1) * P[r2 - l2 + 1][1] % mod[1]) %
          mod[1];
  return 1LL * x * mod[0] + y;
}
unordered_map<long long, int> PA, PB, GA, GB;
int main() {
  scanf("%s%s", a + 1, b + 1);
  int n = strlen(a + 1), m = strlen(b + 1);
  P[0][0] = P[0][1] = 1;
  for (int i = 1; i <= N - 1; ++i)
    for (int j = 0; j <= 1; ++j) P[i][j] = 1LL * P[i - 1][j] * base % mod[j];
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= 1; ++j)
      HA[i][j] = (1LL * HA[i - 1][j] * base + a[i]) % mod[j];
  for (int i = 1; i <= m; ++i)
    for (int j = 0; j <= 1; ++j)
      HB[i][j] = (1LL * HB[i - 1][j] * base + b[i]) % mod[j];
  for (int i = 1; i <= n; ++i) A.s[i] = AR.s[n - i + 1] = a[i];
  for (int i = 1; i <= m; ++i) B.s[i] = BR.s[m - i + 1] = b[i];
  A.build();
  B.build();
  AR.build();
  BR.build();
  long long answer = 1LL * (A.cnt - 1) * (B.cnt - 1);
  for (int i = 2; i <= A.cnt; ++i) {
    int p = A.fail[i];
    PA[Ahasz(A.pos[i] - A.len[i] + 1, A.pos[i])]++;
    if (!p) continue;
    if (2 * A.len[p] >= A.len[i])
      GA[Ahasz(A.pos[i] - (A.len[i] - A.len[p]) + 1, A.pos[i])]++;
  }
  for (int i = 2; i <= B.cnt; ++i) {
    int p = B.fail[i];
    PB[Bhasz(B.pos[i] - B.len[i] + 1, B.pos[i])]++;
    if (!p) continue;
    if (2 * A.len[p] >= B.len[i])
      GB[Bhasz(B.pos[i] - B.len[i] + 1, B.pos[i] - B.len[p])]++;
  }
  for (int i = 2; i <= A.cnt; ++i) {
    int p = A.fail[i];
    if (!p) continue;
    int l = A.pos[i] - (A.len[i] - A.len[p]) + 1, r = A.pos[i];
    if (GB.count(Ahasz(l, r))) answer -= GB[Ahasz(l, r)];
    int dlugosc = A.qw(l, r);
    if (dlugosc == r - l + 1 || dlugosc <= 0) continue;
    int mid = r - dlugosc + 1;
    if (A.czypal(l, mid - 1) == true) {
      long long H1 = Ahasz(l, mid - 1);
      long long H2 = Atwo(l, r, l, mid - 1);
      if (PB.count(H1) && PB.count(H2)) answer--;
      continue;
    }
    dlugosc = AR.qw(n - r + 1, n - l + 1);
    if (dlugosc <= 0) continue;
    mid = l + dlugosc - 1;
    if (A.czypal(mid + 1, r) == true) {
      long long H1 = Ahasz(l, mid);
      long long H2 = Atwo(l, r, l, mid);
      if (PB.count(H1) && PB.count(H2)) answer--;
    }
  }
  for (int i = 2; i <= B.cnt; ++i) {
    int p = B.fail[i];
    if (!p) continue;
    int l = B.pos[i] - B.len[i] + 1, r = B.pos[i] - B.len[p];
    if (GA.count(Bhasz(l, r))) answer -= GA[Bhasz(l, r)];
    int dlugosc = B.qw(l, r);
    if (dlugosc == r - l + 1 || dlugosc <= 0) continue;
    int mid = r - dlugosc + 1;
    if (B.czypal(l, mid - 1) == true) {
      long long H1 = Bhasz(mid, r);
      long long H2 = Btwo(mid, r, l, r);
      if (PA.count(H1) && PA.count(H2)) answer--;
      continue;
    }
    dlugosc = BR.qw(m - r + 1, m - l + 1);
    if (dlugosc <= 0) continue;
    mid = l + dlugosc - 1;
    if (B.czypal(mid + 1, r) == true) {
      long long H1 = Bhasz(mid + 1, r);
      long long H2 = Btwo(mid + 1, r, l, r);
      if (PA.count(H1) && PA.count(H2)) answer--;
    }
  }
  for (int i = 2; i <= A.cnt; ++i) {
    int p = A.fail[i];
    if (!p) continue;
    if (2 * A.len[p] < A.len[i])
      GA[Ahasz(A.pos[i] - (A.len[i] - A.len[p]) + 1, A.pos[i])]++;
  }
  for (int i = 2; i <= B.cnt; ++i) {
    int p = B.fail[i];
    if (!p) continue;
    if (2 * B.len[p] < B.len[i])
      GB[Bhasz(B.pos[i] - B.len[i] + 1, B.pos[i] - B.len[p])]++;
  }
  for (auto it : GA) answer += 1LL * it.second * GB[it.first];
  printf("%lld\n", answer);
  return 0;
}

```