#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 7, M = 30, p1 = 998244353, p2 = 1e9 + 7;
char s[N], t[N];
int n, m, k, d, g1[N], g2[N], g3[N], g4[N];
unordered_map<long long, int> t1, t2, t3;
struct node {
  int a, b, l, w, p;
} e[N], c[N];
inline bool cmp(node a, node b) { return a.l < b.l; }
inline int pows(long long u, int v, int p) {
  long long ans = 1;
  while (v > 0) {
    if (v & 1) ans = ans * u % p;
    u = u * u % p, v = v >> 1;
  }
  return ans;
}
namespace sub1 {
char g[N];
int len, q[N], f1[N], f2[N], h1[N], h2[N], gt[N], fa[N], res[N], ret[N],
    ch[N][M], va[N][M];
inline int getpos(int a, int u) {
  while (a > 0) {
    if (g[u] == g[u - res[a] - 1] && ch[a][s[u] - 'a'] && a > 1)
      return ch[a][s[u] - 'a'];
    if (a == 1 && ch[a][s[u] - 'a']) return ch[a][s[u] - 'a'];
    if (a <= 2) return a;
    a = fa[a];
  }
}
inline void build() { f1[0] = ++len, f2[0] = ++len, fa[1] = 1, fa[2] = 2; }
inline void ins(int u, int t) {
  g[u] = t + 'a';
  int a = f1[u - 1];
  while (a > 2) {
    if (g[u] == g[u - res[a] - 1]) {
      if (!ch[a][t])
        ch[a][t] = ++len, fa[len] = getpos(fa[a], u), res[len] = res[a] + 2;
      f1[u] = ch[a][t];
      break;
    }
    a = fa[a];
  }
  a = f2[u - 1];
  while (a > 2) {
    if (g[u] == g[u - res[a] - 1]) {
      if (!ch[a][t])
        ch[a][t] = ++len, fa[len] = getpos(fa[a], u), res[len] = res[a] + 2;
      f2[u] = ch[a][t];
      break;
    }
    a = fa[a];
  }
  if (!f1[u]) {
    if (!ch[1][t]) ch[1][t] = ++len, res[len] = 1, fa[len] = 1;
    f1[u] = ch[1][t];
  }
  if (!f2[u]) {
    if (g[u] == g[u - 1]) {
      if (!ch[2][t]) ch[2][t] = ++len, res[len] = 2, fa[len] = 2;
      f2[u] = ch[2][t];
    } else
      f2[u] = 2;
  }
  gt[f1[u]] = f2[u], gt[f2[u]] = f1[u];
}
inline void dfs(int u) {
  for (int i = 0; i <= 25; i++) {
    if (!ch[u][i]) continue;
    int x = ch[u][i];
    if (u == 1)
      h1[x] = h2[x] = i + 1;
    else {
      h1[x] = (h1[u] * 29ll + i + 1 + 1ll * g1[res[u] + 1] * (i + 1)) % p1;
      h2[x] = (h2[u] * 29ll + i + 1 + 1ll * g2[res[u] + 1] * (i + 1)) % p2;
    }
    dfs(x);
  }
  if (u <= 2) return;
  long long z = 1000000000ll * h1[u] + h2[u];
  int v = gt[u];
  for (int x = 18; x >= 0; x--)
    if (va[v][x] && res[va[v][x]] >= res[u]) v = va[v][x];
  if (res[v] >= res[u]) v = fa[v];
  k++, e[k].a = h1[u], e[k].b = h2[u], e[k].l = res[u], t1[z] = 1,
       e[k].w = max(res[fa[u]], res[v]);
  if (e[k].w == res[fa[u]])
    e[k].p = fa[u];
  else
    e[k].p = v;
}
inline void bfs() {
  q[++q[0]] = 1, q[++q[0]] = 2;
  for (int i = 1; i <= q[0]; i++) {
    int u = q[i];
    va[u][0] = fa[u];
    for (int x = 1; x <= 18; x++) va[u][x] = va[va[u][x - 1]][x - 1];
    for (int x = 0; x <= 25; x++)
      if (ch[u][x]) q[++q[0]] = ch[u][x];
  }
}
}  // namespace sub1
namespace sub2 {
char g[N];
int len, q[N], gt[N], f1[N], f2[N], h1[N], h2[N], fa[N], res[N], ch[N][M],
    va[N][M];
inline int getpos(int a, int u) {
  while (a > 0) {
    if (g[u] == g[u - res[a] - 1] && ch[a][g[u] - 'a'] && a > 1)
      return ch[a][g[u] - 'a'];
    if (a == 1 && ch[a][g[u] - 'a']) return ch[a][g[u] - 'a'];
    if (a <= 2) return a;
    a = fa[a];
  }
}
inline void build() { f1[0] = ++len, f2[0] = ++len, fa[1] = 1, fa[2] = 2; }
inline void ins(int u, int t) {
  g[u] = t + 'a';
  int a = f1[u - 1];
  while (a > 2) {
    if (g[u] == g[u - res[a] - 1]) {
      if (!ch[a][t])
        ch[a][t] = ++len, fa[len] = getpos(fa[a], u), res[len] = res[a] + 2;
      f1[u] = ch[a][t];
      break;
    }
    a = fa[a];
  }
  a = f2[u - 1];
  while (a > 2) {
    if (g[u] == g[u - res[a] - 1]) {
      if (!ch[a][t])
        ch[a][t] = ++len, fa[len] = getpos(fa[a], u), res[len] = res[a] + 2;
      f2[u] = ch[a][t];
      break;
    }
    a = fa[a];
  }
  if (!f1[u]) {
    if (!ch[1][t]) ch[1][t] = ++len, res[len] = 1, fa[len] = 1;
    f1[u] = ch[1][t];
  }
  if (!f2[u]) {
    if (g[u] == g[u - 1]) {
      if (!ch[2][t]) ch[2][t] = ++len, res[len] = 2, fa[len] = 2;
      f2[u] = ch[2][t];
    } else
      f2[u] = 2;
  }
  gt[f1[u]] = f2[u], gt[f2[u]] = f1[u];
}
inline void dfs(int u) {
  for (int i = 0; i <= 25; i++) {
    if (!ch[u][i]) continue;
    int x = ch[u][i];
    if (u == 1)
      h1[x] = h2[x] = i + 1;
    else {
      h1[x] = (h1[u] * 29ll + i + 1 + 1ll * g1[res[u] + 1] * (i + 1)) % p1;
      h2[x] = (h2[u] * 29ll + i + 1 + 1ll * g2[res[u] + 1] * (i + 1)) % p2;
    }
    dfs(x);
  }
  if (u <= 2) return;
  long long z = 1000000000ll * h1[u] + h2[u];
  int v = gt[u];
  for (int x = 18; x >= 0; x--)
    if (va[v][x] && res[va[v][x]] >= res[u]) v = va[v][x];
  if (res[v] >= res[u]) v = fa[v];
  d++, c[d].a = h1[u], c[d].b = h2[u], c[d].l = res[u], t2[z] = 1,
       c[d].w = max(res[fa[u]], res[v]);
  if (c[d].w == res[fa[u]])
    c[d].p = fa[u];
  else
    c[d].p = v;
}
inline void bfs() {
  q[++q[0]] = 1, q[++q[0]] = 2;
  for (int i = 1; i <= q[0]; i++) {
    int u = q[i];
    va[u][0] = fa[u];
    for (int x = 1; x <= 18; x++) va[u][x] = va[va[u][x - 1]][x - 1];
    for (int x = 0; x <= 25; x++)
      if (ch[u][x]) q[++q[0]] = ch[u][x];
  }
}
}  // namespace sub2
int main() {
  scanf("%s%s", s + 1, t + 1), n = strlen(s + 1), m = strlen(t + 1);
  g1[0] = g2[0] = g3[0] = g4[0] = 1, g1[1] = g2[1] = 29,
  g3[1] = pows(29, p1 - 2, p1), g4[1] = pows(29, p2 - 2, p2);
  for (int i = 2; i <= n + m; i++) {
    g1[i] = 1ll * g1[1] * g1[i - 1] % p1, g2[i] = 1ll * g2[1] * g2[i - 1] % p2;
    g3[i] = 1ll * g3[1] * g3[i - 1] % p1, g4[i] = 1ll * g4[1] * g4[i - 1] % p2;
  }
  sub1::build(), sub2::build();
  for (int i = 1; i <= n; i++) sub1::ins(i, s[i] - 'a');
  for (int i = 1; i <= m; i++) sub2::ins(i, t[i] - 'a');
  sub1::bfs(), sub1::dfs(1), sub1::dfs(2);
  sub2::bfs(), sub2::dfs(1), sub2::dfs(2);
  long long ans = 1ll * (sub1::len - 2) * (sub2::len - 2);
  sort(e + 1, e + k + 1, cmp), sort(c + 1, c + d + 1, cmp);
  for (int i = 1; i <= k; i++) {
    if (!e[i].w || e[i].w * 2 > e[i].l) continue;
    long long va =
        (e[i].a - 1ll * g1[e[i].l - e[i].w] * sub1::h1[e[i].p] % p1 + p1) % p1;
    long long vb =
        (e[i].b - 1ll * g2[e[i].l - e[i].w] * sub1::h2[e[i].p] % p2 + p2) % p2;
    long long v1 = sub1::h1[e[i].p], v2 = sub1::h2[e[i].p];
    long long v3 = (va - v1 + p1) * g3[e[i].w] % p1,
              v4 = (vb - v2 + p2) * g4[e[i].w] % p2;
    long long vc = (v3 + v1 * g1[e[i].l - e[i].w * 2]) % p1,
              vd = (v4 + v2 * g2[e[i].l - e[i].w * 2]) % p2;
    if (v3 == 0 && v4 == 0) v3 = va, v4 = vb;
    int s1 = 0, s2 = 0, l = e[i].w;
    for (int x = 1; x <= n; x++) {
      long long z = 1000000000ll * v1 + v2;
      if (!t1[z]) break;
      s1 = x;
      v1 = (v1 + 1ll * g1[l] * vc) % p1, v2 = (v2 + 1ll * g2[l] * vd) % p2,
      l += (e[i].l - e[i].w);
    }
    l = e[i].l - e[i].w * 2;
    if (l == 0) l = e[i].w;
    for (int x = 1; x <= n; x++) {
      long long z = 1000000000ll * v3 + v4;
      if (!t2[z]) break;
      s2 = x;
      if (x == 2) t3[z] = max(t3[z], l - e[i].l + e[i].w);
      v3 = (v3 + 1ll * g1[l] * va) % p1, v4 = (v4 + 1ll * g2[l] * vb) % p2,
      l += (e[i].l - e[i].w);
    }
    if (s1 == 0 || s2 == 0) continue;
    ans = ans - 1ll * s1 * s2 + s1 + s2 - 1;
  }
  for (int i = 1; i <= d; i++) {
    if (!c[i].w || c[i].w * 2 > c[i].l) continue;
    long long z = 1000000000ll * c[i].a + c[i].b;
    if (t3[z] == c[i].w) continue;
    e[i] = c[i];
    long long va =
        (e[i].a - 1ll * g1[e[i].l - e[i].w] * sub2::h1[e[i].p] % p1 + p1) % p1;
    long long vb =
        (e[i].b - 1ll * g2[e[i].l - e[i].w] * sub2::h2[e[i].p] % p2 + p2) % p2;
    long long v1 = sub2::h1[e[i].p], v2 = sub2::h2[e[i].p];
    long long v3 = (va - v1 + p1) * g3[e[i].w] % p1,
              v4 = (vb - v2 + p2) * g4[e[i].w] % p2;
    long long vc = (v3 + v1 * g1[e[i].l - e[i].w * 2]) % p1,
              vd = (v4 + v2 * g2[e[i].l - e[i].w * 2]) % p2;
    if (v3 == 0 && v4 == 0) v3 = va, v4 = vb;
    int s1 = 0, s2 = 0, l = e[i].w;
    for (int x = 1; x <= n; x++) {
      long long z = 1000000000ll * v1 + v2;
      if (!t2[z]) break;
      s1 = x;
      v1 = (v1 + 1ll * g1[l] * vc) % p1, v2 = (v2 + 1ll * g2[l] * vd) % p2,
      l += (e[i].l - e[i].w);
    }
    l = e[i].l - e[i].w * 2;
    if (l == 0) l = e[i].w;
    for (int x = 1; x <= n; x++) {
      long long z = 1000000000ll * v3 + v4;
      if (!t1[z]) break;
      s2 = x;
      v3 = (v3 + 1ll * g1[l] * va) % p1, v4 = (v4 + 1ll * g2[l] * vb) % p2,
      l += (e[i].l - e[i].w);
    }
    if (s1 == 0 || s2 == 0) continue;
    ans = ans - 1ll * s1 * s2 + s1 + s2 - 1;
  }
  cout << ans << endl;
}

### 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;
const int N = 4e5 + 7, M = 30, p1 = 998244353, p2 = 1e9 + 7;
char s[N], t[N];
int n, m, k, d, g1[N], g2[N], g3[N], g4[N];
unordered_map<long long, int> t1, t2, t3;
struct node {
  int a, b, l, w, p;
} e[N], c[N];
inline bool cmp(node a, node b) { return a.l < b.l; }
inline int pows(long long u, int v, int p) {
  long long ans = 1;
  while (v > 0) {
    if (v & 1) ans = ans * u % p;
    u = u * u % p, v = v >> 1;
  }
  return ans;
}
namespace sub1 {
char g[N];
int len, q[N], f1[N], f2[N], h1[N], h2[N], gt[N], fa[N], res[N], ret[N],
    ch[N][M], va[N][M];
inline int getpos(int a, int u) {
  while (a > 0) {
    if (g[u] == g[u - res[a] - 1] && ch[a][s[u] - 'a'] && a > 1)
      return ch[a][s[u] - 'a'];
    if (a == 1 && ch[a][s[u] - 'a']) return ch[a][s[u] - 'a'];
    if (a <= 2) return a;
    a = fa[a];
  }
}
inline void build() { f1[0] = ++len, f2[0] = ++len, fa[1] = 1, fa[2] = 2; }
inline void ins(int u, int t) {
  g[u] = t + 'a';
  int a = f1[u - 1];
  while (a > 2) {
    if (g[u] == g[u - res[a] - 1]) {
      if (!ch[a][t])
        ch[a][t] = ++len, fa[len] = getpos(fa[a], u), res[len] = res[a] + 2;
      f1[u] = ch[a][t];
      break;
    }
    a = fa[a];
  }
  a = f2[u - 1];
  while (a > 2) {
    if (g[u] == g[u - res[a] - 1]) {
      if (!ch[a][t])
        ch[a][t] = ++len, fa[len] = getpos(fa[a], u), res[len] = res[a] + 2;
      f2[u] = ch[a][t];
      break;
    }
    a = fa[a];
  }
  if (!f1[u]) {
    if (!ch[1][t]) ch[1][t] = ++len, res[len] = 1, fa[len] = 1;
    f1[u] = ch[1][t];
  }
  if (!f2[u]) {
    if (g[u] == g[u - 1]) {
      if (!ch[2][t]) ch[2][t] = ++len, res[len] = 2, fa[len] = 2;
      f2[u] = ch[2][t];
    } else
      f2[u] = 2;
  }
  gt[f1[u]] = f2[u], gt[f2[u]] = f1[u];
}
inline void dfs(int u) {
  for (int i = 0; i <= 25; i++) {
    if (!ch[u][i]) continue;
    int x = ch[u][i];
    if (u == 1)
      h1[x] = h2[x] = i + 1;
    else {
      h1[x] = (h1[u] * 29ll + i + 1 + 1ll * g1[res[u] + 1] * (i + 1)) % p1;
      h2[x] = (h2[u] * 29ll + i + 1 + 1ll * g2[res[u] + 1] * (i + 1)) % p2;
    }
    dfs(x);
  }
  if (u <= 2) return;
  long long z = 1000000000ll * h1[u] + h2[u];
  int v = gt[u];
  for (int x = 18; x >= 0; x--)
    if (va[v][x] && res[va[v][x]] >= res[u]) v = va[v][x];
  if (res[v] >= res[u]) v = fa[v];
  k++, e[k].a = h1[u], e[k].b = h2[u], e[k].l = res[u], t1[z] = 1,
       e[k].w = max(res[fa[u]], res[v]);
  if (e[k].w == res[fa[u]])
    e[k].p = fa[u];
  else
    e[k].p = v;
}
inline void bfs() {
  q[++q[0]] = 1, q[++q[0]] = 2;
  for (int i = 1; i <= q[0]; i++) {
    int u = q[i];
    va[u][0] = fa[u];
    for (int x = 1; x <= 18; x++) va[u][x] = va[va[u][x - 1]][x - 1];
    for (int x = 0; x <= 25; x++)
      if (ch[u][x]) q[++q[0]] = ch[u][x];
  }
}
}  // namespace sub1
namespace sub2 {
char g[N];
int len, q[N], gt[N], f1[N], f2[N], h1[N], h2[N], fa[N], res[N], ch[N][M],
    va[N][M];
inline int getpos(int a, int u) {
  while (a > 0) {
    if (g[u] == g[u - res[a] - 1] && ch[a][g[u] - 'a'] && a > 1)
      return ch[a][g[u] - 'a'];
    if (a == 1 && ch[a][g[u] - 'a']) return ch[a][g[u] - 'a'];
    if (a <= 2) return a;
    a = fa[a];
  }
}
inline void build() { f1[0] = ++len, f2[0] = ++len, fa[1] = 1, fa[2] = 2; }
inline void ins(int u, int t) {
  g[u] = t + 'a';
  int a = f1[u - 1];
  while (a > 2) {
    if (g[u] == g[u - res[a] - 1]) {
      if (!ch[a][t])
        ch[a][t] = ++len, fa[len] = getpos(fa[a], u), res[len] = res[a] + 2;
      f1[u] = ch[a][t];
      break;
    }
    a = fa[a];
  }
  a = f2[u - 1];
  while (a > 2) {
    if (g[u] == g[u - res[a] - 1]) {
      if (!ch[a][t])
        ch[a][t] = ++len, fa[len] = getpos(fa[a], u), res[len] = res[a] + 2;
      f2[u] = ch[a][t];
      break;
    }
    a = fa[a];
  }
  if (!f1[u]) {
    if (!ch[1][t]) ch[1][t] = ++len, res[len] = 1, fa[len] = 1;
    f1[u] = ch[1][t];
  }
  if (!f2[u]) {
    if (g[u] == g[u - 1]) {
      if (!ch[2][t]) ch[2][t] = ++len, res[len] = 2, fa[len] = 2;
      f2[u] = ch[2][t];
    } else
      f2[u] = 2;
  }
  gt[f1[u]] = f2[u], gt[f2[u]] = f1[u];
}
inline void dfs(int u) {
  for (int i = 0; i <= 25; i++) {
    if (!ch[u][i]) continue;
    int x = ch[u][i];
    if (u == 1)
      h1[x] = h2[x] = i + 1;
    else {
      h1[x] = (h1[u] * 29ll + i + 1 + 1ll * g1[res[u] + 1] * (i + 1)) % p1;
      h2[x] = (h2[u] * 29ll + i + 1 + 1ll * g2[res[u] + 1] * (i + 1)) % p2;
    }
    dfs(x);
  }
  if (u <= 2) return;
  long long z = 1000000000ll * h1[u] + h2[u];
  int v = gt[u];
  for (int x = 18; x >= 0; x--)
    if (va[v][x] && res[va[v][x]] >= res[u]) v = va[v][x];
  if (res[v] >= res[u]) v = fa[v];
  d++, c[d].a = h1[u], c[d].b = h2[u], c[d].l = res[u], t2[z] = 1,
       c[d].w = max(res[fa[u]], res[v]);
  if (c[d].w == res[fa[u]])
    c[d].p = fa[u];
  else
    c[d].p = v;
}
inline void bfs() {
  q[++q[0]] = 1, q[++q[0]] = 2;
  for (int i = 1; i <= q[0]; i++) {
    int u = q[i];
    va[u][0] = fa[u];
    for (int x = 1; x <= 18; x++) va[u][x] = va[va[u][x - 1]][x - 1];
    for (int x = 0; x <= 25; x++)
      if (ch[u][x]) q[++q[0]] = ch[u][x];
  }
}
}  // namespace sub2
int main() {
  scanf("%s%s", s + 1, t + 1), n = strlen(s + 1), m = strlen(t + 1);
  g1[0] = g2[0] = g3[0] = g4[0] = 1, g1[1] = g2[1] = 29,
  g3[1] = pows(29, p1 - 2, p1), g4[1] = pows(29, p2 - 2, p2);
  for (int i = 2; i <= n + m; i++) {
    g1[i] = 1ll * g1[1] * g1[i - 1] % p1, g2[i] = 1ll * g2[1] * g2[i - 1] % p2;
    g3[i] = 1ll * g3[1] * g3[i - 1] % p1, g4[i] = 1ll * g4[1] * g4[i - 1] % p2;
  }
  sub1::build(), sub2::build();
  for (int i = 1; i <= n; i++) sub1::ins(i, s[i] - 'a');
  for (int i = 1; i <= m; i++) sub2::ins(i, t[i] - 'a');
  sub1::bfs(), sub1::dfs(1), sub1::dfs(2);
  sub2::bfs(), sub2::dfs(1), sub2::dfs(2);
  long long ans = 1ll * (sub1::len - 2) * (sub2::len - 2);
  sort(e + 1, e + k + 1, cmp), sort(c + 1, c + d + 1, cmp);
  for (int i = 1; i <= k; i++) {
    if (!e[i].w || e[i].w * 2 > e[i].l) continue;
    long long va =
        (e[i].a - 1ll * g1[e[i].l - e[i].w] * sub1::h1[e[i].p] % p1 + p1) % p1;
    long long vb =
        (e[i].b - 1ll * g2[e[i].l - e[i].w] * sub1::h2[e[i].p] % p2 + p2) % p2;
    long long v1 = sub1::h1[e[i].p], v2 = sub1::h2[e[i].p];
    long long v3 = (va - v1 + p1) * g3[e[i].w] % p1,
              v4 = (vb - v2 + p2) * g4[e[i].w] % p2;
    long long vc = (v3 + v1 * g1[e[i].l - e[i].w * 2]) % p1,
              vd = (v4 + v2 * g2[e[i].l - e[i].w * 2]) % p2;
    if (v3 == 0 && v4 == 0) v3 = va, v4 = vb;
    int s1 = 0, s2 = 0, l = e[i].w;
    for (int x = 1; x <= n; x++) {
      long long z = 1000000000ll * v1 + v2;
      if (!t1[z]) break;
      s1 = x;
      v1 = (v1 + 1ll * g1[l] * vc) % p1, v2 = (v2 + 1ll * g2[l] * vd) % p2,
      l += (e[i].l - e[i].w);
    }
    l = e[i].l - e[i].w * 2;
    if (l == 0) l = e[i].w;
    for (int x = 1; x <= n; x++) {
      long long z = 1000000000ll * v3 + v4;
      if (!t2[z]) break;
      s2 = x;
      if (x == 2) t3[z] = max(t3[z], l - e[i].l + e[i].w);
      v3 = (v3 + 1ll * g1[l] * va) % p1, v4 = (v4 + 1ll * g2[l] * vb) % p2,
      l += (e[i].l - e[i].w);
    }
    if (s1 == 0 || s2 == 0) continue;
    ans = ans - 1ll * s1 * s2 + s1 + s2 - 1;
  }
  for (int i = 1; i <= d; i++) {
    if (!c[i].w || c[i].w * 2 > c[i].l) continue;
    long long z = 1000000000ll * c[i].a + c[i].b;
    if (t3[z] == c[i].w) continue;
    e[i] = c[i];
    long long va =
        (e[i].a - 1ll * g1[e[i].l - e[i].w] * sub2::h1[e[i].p] % p1 + p1) % p1;
    long long vb =
        (e[i].b - 1ll * g2[e[i].l - e[i].w] * sub2::h2[e[i].p] % p2 + p2) % p2;
    long long v1 = sub2::h1[e[i].p], v2 = sub2::h2[e[i].p];
    long long v3 = (va - v1 + p1) * g3[e[i].w] % p1,
              v4 = (vb - v2 + p2) * g4[e[i].w] % p2;
    long long vc = (v3 + v1 * g1[e[i].l - e[i].w * 2]) % p1,
              vd = (v4 + v2 * g2[e[i].l - e[i].w * 2]) % p2;
    if (v3 == 0 && v4 == 0) v3 = va, v4 = vb;
    int s1 = 0, s2 = 0, l = e[i].w;
    for (int x = 1; x <= n; x++) {
      long long z = 1000000000ll * v1 + v2;
      if (!t2[z]) break;
      s1 = x;
      v1 = (v1 + 1ll * g1[l] * vc) % p1, v2 = (v2 + 1ll * g2[l] * vd) % p2,
      l += (e[i].l - e[i].w);
    }
    l = e[i].l - e[i].w * 2;
    if (l == 0) l = e[i].w;
    for (int x = 1; x <= n; x++) {
      long long z = 1000000000ll * v3 + v4;
      if (!t1[z]) break;
      s2 = x;
      v3 = (v3 + 1ll * g1[l] * va) % p1, v4 = (v4 + 1ll * g2[l] * vb) % p2,
      l += (e[i].l - e[i].w);
    }
    if (s1 == 0 || s2 == 0) continue;
    ans = ans - 1ll * s1 * s2 + s1 + s2 - 1;
  }
  cout << ans << endl;
}

```