#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int IMAGROOTID = 0;
const int ZEROROOTID = 1;
const int ALPH = 26;
struct PalTreeNode {
  int firststart, len, suff, nxt[ALPH];
  PalTreeNode() {
    firststart = len = suff = -1;
    memset(nxt, -1, sizeof(nxt));
  }
};
struct PalTree {
  char *s;
  int slen;
  int lg;
  vector<PalTreeNode> nodes;
  int nnodes;
  vector<int> longest;
  vector<vector<int>> up;
  void init(char *_s) {
    s = _s;
    slen = strlen(s);
    nodes = vector<PalTreeNode>(slen + 2);
    nodes[IMAGROOTID].len = -1, nodes[IMAGROOTID].suff = IMAGROOTID;
    nodes[ZEROROOTID].len = 0, nodes[ZEROROOTID].suff = IMAGROOTID, nnodes = 2;
    longest = vector<int>(slen);
  }
  int augment(int at, int idx) {
    while (s[idx] != s[idx - nodes[at].len - 1]) at = nodes[at].suff;
    int &to = nodes[at].nxt[s[idx] - 'a'];
    if (to == -1) {
      to = nnodes++;
      nodes[to].firststart = idx - nodes[at].len - 1;
      nodes[to].len = nodes[at].len + 2;
      at = nodes[at].suff;
      while (s[idx] != s[idx - nodes[at].len - 1]) at = nodes[at].suff;
      nodes[to].suff =
          nodes[to].len == 1 ? ZEROROOTID : nodes[at].nxt[s[idx] - 'a'];
    }
    return to;
  }
  void build() {
    for (int i = (0); i < (slen); ++i)
      longest[i] = augment(i == 0 ? IMAGROOTID : longest[i - 1], i);
    lg = 0;
    while ((2 << lg) < nnodes) ++lg;
    up = vector<vector<int>>(nnodes, vector<int>(lg + 1));
    for (int i = (0); i < (nnodes); ++i) up[i][0] = nodes[i].suff;
    for (int k = (0); k < (lg); ++k)
      for (int i = (0); i < (nnodes); ++i) up[i][k + 1] = up[up[i][k]][k];
  }
  int query(int idx, int lim) const {
    int at = longest[idx];
    if (nodes[at].len <= lim) return nodes[at].len;
    for (int k = lg; k >= 0; --k)
      if (nodes[up[at][k]].len > lim) at = up[at][k];
    return nodes[nodes[at].suff].len;
  }
};
const int HMOD[] = {1000000007, 1000000009};
const int HMLT = 2333;
struct HashNode {
  int a, b;
  HashNode() {}
  HashNode(int a, int b) : a(a), b(b) {}
  long long val() { return (long long)a * HMOD[1] + b; }
};
HashNode operator*(const HashNode &p, const int &x) {
  return HashNode((long long)p.a * x % HMOD[0], (long long)p.b * x % HMOD[1]);
}
HashNode operator+(const HashNode &p, const int &x) {
  return HashNode((p.a + x) % HMOD[0], (p.b + x) % HMOD[1]);
}
HashNode operator*(const HashNode &p, const HashNode &q) {
  return HashNode((long long)p.a * q.a % HMOD[0],
                  (long long)p.b * q.b % HMOD[1]);
}
HashNode operator+(const HashNode &p, const HashNode &q) {
  return HashNode((p.a + q.a) % HMOD[0], (p.b + q.b) % HMOD[1]);
}
HashNode operator-(const HashNode &p, const HashNode &q) {
  return HashNode((p.a + HMOD[0] - q.a) % HMOD[0],
                  (p.b + HMOD[1] - q.b) % HMOD[1]);
}
struct Hash {
  char *s;
  int slen;
  vector<HashNode> hval, hpw;
  void init(char *_s) {
    s = _s;
    slen = strlen(s);
    hval = hpw = vector<HashNode>(slen + 1);
  }
  void build() {
    hval[0] = HashNode(0, 0), hpw[0] = HashNode(1, 1);
    for (int i = (0); i < (slen); ++i)
      hval[i + 1] = hval[i] * HMLT + (s[i] - 'a' + 1),
               hpw[i + 1] = hpw[i] * HMLT;
  }
  HashNode get(int l, int r) const {
    return hval[r + 1] - hval[l] * hpw[r - l + 1];
  }
};
HashNode gettrihash(const Hash &h, int al, int ar, int bl, int br, int cl,
                    int cr) {
  return (h.get(al, ar) * h.hpw[br - bl + 1] + h.get(bl, br)) *
             h.hpw[cr - cl + 1] +
         h.get(cl, cr);
}
bool decompose(const PalTree &fw, const PalTree &bw, int len, int al, int ar,
               int &bl, int &br, int &cl, int &cr) {
  int palsuff = fw.query(ar, ar - al + 1), wantpref = ar - al + 1 - palsuff;
  if (wantpref != 0 && bw.query(len - al - 1, wantpref) == wantpref) {
    bl = al, br = al + wantpref - 1, cl = al + wantpref, cr = ar;
    return true;
  }
  int palpref = bw.query(len - al - 1, ar - al + 1),
      wantsuff = ar - al + 1 - palpref;
  if (wantpref != 0 && fw.query(ar, wantsuff) == wantsuff) {
    bl = al, br = al + palpref - 1, cl = al + palpref, cr = ar;
    return true;
  }
  return false;
}
const int MAXLEN = 200000;
char a[MAXLEN + 1];
int alen;
char b[MAXLEN + 1];
int blen;
char arev[MAXLEN + 1];
char brev[MAXLEN + 1];
PalTree ta, tb, tarev, tbrev;
Hash ha, hb;
map<long long, int> acnt;
map<long long, int> bcnt;
map<long long, int> asuff;
map<long long, int> bpref;
int safeget(const map<long long, int> &mp, long long key) {
  auto it = mp.find(key);
  return it != mp.end() ? it->second : 0;
}
long long solve() {
  for (int i = (0); i < (alen); ++i) arev[alen - i - 1] = a[i];
  arev[alen] = '\0';
  for (int i = (0); i < (blen); ++i) brev[blen - i - 1] = b[i];
  brev[blen] = '\0';
  ta.init(a);
  ta.build();
  tb.init(b);
  tb.build();
  tarev.init(arev);
  tarev.build();
  tbrev.init(brev);
  tbrev.build();
  ha.init(a);
  ha.build();
  hb.init(b);
  hb.build();
  acnt.clear();
  bcnt.clear();
  asuff.clear();
  bpref.clear();
  long long ret = (long long)(ta.nnodes - 2) * (tb.nnodes - 2);
  for (int i = (2); i < (ta.nnodes); ++i) {
    int pl = ta.nodes[i].firststart,
        pr = ta.nodes[i].firststart + ta.nodes[i].len - 1;
    acnt[ha.get(pl, pr).val()]++;
    if (ta.nodes[i].suff < 2) continue;
    int vl = pl + ta.nodes[ta.nodes[i].suff].len, vr = pr;
    asuff[ha.get(vl, vr).val()]++;
  }
  for (int i = (2); i < (tb.nnodes); ++i) {
    int pl = tb.nodes[i].firststart,
        pr = tb.nodes[i].firststart + tb.nodes[i].len - 1;
    bcnt[hb.get(pl, pr).val()]++;
    if (tb.nodes[i].suff < 2) continue;
    int vl = pl, vr = pr - tb.nodes[tb.nodes[i].suff].len;
    bpref[hb.get(vl, vr).val()]++;
  }
  for (int i = (2); i < (ta.nnodes); ++i) {
    int pl = ta.nodes[i].firststart,
        pr = ta.nodes[i].firststart + ta.nodes[i].len - 1;
    if (ta.nodes[i].suff < 2) continue;
    int vl = pl + ta.nodes[ta.nodes[i].suff].len, vr = pr, xl = pl, xr = vl - 1;
    if (vr - vl <= xr - xl) ret -= safeget(bpref, ha.get(vl, vr).val());
    int wl, wr, yl, yr;
    if (decompose(ta, tarev, alen, vl, vr, yl, yr, wl, wr))
      ret -= safeget(bcnt, gettrihash(ha, yl, yr, wl, wr, yl, yr).val());
  }
  for (int i = (2); i < (tb.nnodes); ++i) {
    int pl = tb.nodes[i].firststart,
        pr = tb.nodes[i].firststart + tb.nodes[i].len - 1;
    if (tb.nodes[i].suff < 2) continue;
    int vl = pl, vr = pr - tb.nodes[tb.nodes[i].suff].len, xl = vr + 1, xr = pr;
    if (vr - vl <= xr - xl) ret -= safeget(asuff, hb.get(vl, vr).val());
    int wl, wr, yl, yr;
    if (decompose(tb, tbrev, blen, vl, vr, wl, wr, yl, yr))
      ret -= safeget(acnt, gettrihash(hb, yl, yr, wl, wr, yl, yr).val());
  }
  for (auto it = asuff.begin(); it != asuff.end(); ++it)
    ret += (long long)it->second * safeget(bpref, it->first);
  return ret;
}
void run() {
  scanf("%s", a);
  alen = strlen(a);
  scanf("%s", b);
  blen = strlen(b);
  printf("%lld\n", solve());
}
bool ispal(char *s, int i, int j) {
  while (i <= j) {
    if (s[i] != s[j]) return false;
    ++i, --j;
  }
  return true;
}
long long bfsolve() {
  set<string> apal;
  for (int i = (0); i < (alen); ++i)
    for (int j = (i); j < (alen); ++j)
      if (ispal(a, i, j)) apal.insert(string(a + i, a + j + 1));
  set<string> bpal;
  for (int i = (0); i < (blen); ++i)
    for (int j = (i); j < (blen); ++j)
      if (ispal(b, i, j)) bpal.insert(string(b + i, b + j + 1));
  set<string> ret;
  for (auto ait = apal.begin(); ait != apal.end(); ++ait)
    for (auto bit = bpal.begin(); bit != bpal.end(); ++bit)
      ret.insert(*ait + *bit);
  return ((int)(ret).size());
}
void stress1() {
  int t = 0;
  for (alen = 1; alen <= 10; ++alen)
    for (blen = 1; blen <= 10; ++blen)
      for (int amask = (0); amask < (1 << alen); ++amask)
        for (int bmask = (0); bmask < (1 << blen); ++bmask) {
          for (int i = (0); i < (alen); ++i)
            a[i] = (amask & (1 << i)) == 0 ? 'x' : 'y';
          a[alen] = '\0';
          for (int i = (0); i < (blen); ++i)
            b[i] = (bmask & (1 << i)) == 0 ? 'x' : 'y';
          b[blen] = '\0';
          long long have = solve();
          long long want = bfsolve();
          if (have == want) {
            if (++t % 1000 == 0) printf(".");
            continue;
          }
          printf("err a=%s b=%s have=%lld want=%lld\n", a, b, have, want);
          return;
        }
}
void stress2() {
  for (int rep = (0); rep < (10); ++rep) {
    alen = MAXLEN;
    for (int i = (0); i < (alen); ++i) a[i] = 'a' + rand() % 26;
    a[alen] = '\0';
    blen = MAXLEN;
    for (int i = (0); i < (blen); ++i) b[i] = 'a' + rand() % 26;
    b[blen] = '\0';
    long long have = solve();
    printf("%lld\n", have);
  }
}
int main() {
  run();
  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 gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int IMAGROOTID = 0;
const int ZEROROOTID = 1;
const int ALPH = 26;
struct PalTreeNode {
  int firststart, len, suff, nxt[ALPH];
  PalTreeNode() {
    firststart = len = suff = -1;
    memset(nxt, -1, sizeof(nxt));
  }
};
struct PalTree {
  char *s;
  int slen;
  int lg;
  vector<PalTreeNode> nodes;
  int nnodes;
  vector<int> longest;
  vector<vector<int>> up;
  void init(char *_s) {
    s = _s;
    slen = strlen(s);
    nodes = vector<PalTreeNode>(slen + 2);
    nodes[IMAGROOTID].len = -1, nodes[IMAGROOTID].suff = IMAGROOTID;
    nodes[ZEROROOTID].len = 0, nodes[ZEROROOTID].suff = IMAGROOTID, nnodes = 2;
    longest = vector<int>(slen);
  }
  int augment(int at, int idx) {
    while (s[idx] != s[idx - nodes[at].len - 1]) at = nodes[at].suff;
    int &to = nodes[at].nxt[s[idx] - 'a'];
    if (to == -1) {
      to = nnodes++;
      nodes[to].firststart = idx - nodes[at].len - 1;
      nodes[to].len = nodes[at].len + 2;
      at = nodes[at].suff;
      while (s[idx] != s[idx - nodes[at].len - 1]) at = nodes[at].suff;
      nodes[to].suff =
          nodes[to].len == 1 ? ZEROROOTID : nodes[at].nxt[s[idx] - 'a'];
    }
    return to;
  }
  void build() {
    for (int i = (0); i < (slen); ++i)
      longest[i] = augment(i == 0 ? IMAGROOTID : longest[i - 1], i);
    lg = 0;
    while ((2 << lg) < nnodes) ++lg;
    up = vector<vector<int>>(nnodes, vector<int>(lg + 1));
    for (int i = (0); i < (nnodes); ++i) up[i][0] = nodes[i].suff;
    for (int k = (0); k < (lg); ++k)
      for (int i = (0); i < (nnodes); ++i) up[i][k + 1] = up[up[i][k]][k];
  }
  int query(int idx, int lim) const {
    int at = longest[idx];
    if (nodes[at].len <= lim) return nodes[at].len;
    for (int k = lg; k >= 0; --k)
      if (nodes[up[at][k]].len > lim) at = up[at][k];
    return nodes[nodes[at].suff].len;
  }
};
const int HMOD[] = {1000000007, 1000000009};
const int HMLT = 2333;
struct HashNode {
  int a, b;
  HashNode() {}
  HashNode(int a, int b) : a(a), b(b) {}
  long long val() { return (long long)a * HMOD[1] + b; }
};
HashNode operator*(const HashNode &p, const int &x) {
  return HashNode((long long)p.a * x % HMOD[0], (long long)p.b * x % HMOD[1]);
}
HashNode operator+(const HashNode &p, const int &x) {
  return HashNode((p.a + x) % HMOD[0], (p.b + x) % HMOD[1]);
}
HashNode operator*(const HashNode &p, const HashNode &q) {
  return HashNode((long long)p.a * q.a % HMOD[0],
                  (long long)p.b * q.b % HMOD[1]);
}
HashNode operator+(const HashNode &p, const HashNode &q) {
  return HashNode((p.a + q.a) % HMOD[0], (p.b + q.b) % HMOD[1]);
}
HashNode operator-(const HashNode &p, const HashNode &q) {
  return HashNode((p.a + HMOD[0] - q.a) % HMOD[0],
                  (p.b + HMOD[1] - q.b) % HMOD[1]);
}
struct Hash {
  char *s;
  int slen;
  vector<HashNode> hval, hpw;
  void init(char *_s) {
    s = _s;
    slen = strlen(s);
    hval = hpw = vector<HashNode>(slen + 1);
  }
  void build() {
    hval[0] = HashNode(0, 0), hpw[0] = HashNode(1, 1);
    for (int i = (0); i < (slen); ++i)
      hval[i + 1] = hval[i] * HMLT + (s[i] - 'a' + 1),
               hpw[i + 1] = hpw[i] * HMLT;
  }
  HashNode get(int l, int r) const {
    return hval[r + 1] - hval[l] * hpw[r - l + 1];
  }
};
HashNode gettrihash(const Hash &h, int al, int ar, int bl, int br, int cl,
                    int cr) {
  return (h.get(al, ar) * h.hpw[br - bl + 1] + h.get(bl, br)) *
             h.hpw[cr - cl + 1] +
         h.get(cl, cr);
}
bool decompose(const PalTree &fw, const PalTree &bw, int len, int al, int ar,
               int &bl, int &br, int &cl, int &cr) {
  int palsuff = fw.query(ar, ar - al + 1), wantpref = ar - al + 1 - palsuff;
  if (wantpref != 0 && bw.query(len - al - 1, wantpref) == wantpref) {
    bl = al, br = al + wantpref - 1, cl = al + wantpref, cr = ar;
    return true;
  }
  int palpref = bw.query(len - al - 1, ar - al + 1),
      wantsuff = ar - al + 1 - palpref;
  if (wantpref != 0 && fw.query(ar, wantsuff) == wantsuff) {
    bl = al, br = al + palpref - 1, cl = al + palpref, cr = ar;
    return true;
  }
  return false;
}
const int MAXLEN = 200000;
char a[MAXLEN + 1];
int alen;
char b[MAXLEN + 1];
int blen;
char arev[MAXLEN + 1];
char brev[MAXLEN + 1];
PalTree ta, tb, tarev, tbrev;
Hash ha, hb;
map<long long, int> acnt;
map<long long, int> bcnt;
map<long long, int> asuff;
map<long long, int> bpref;
int safeget(const map<long long, int> &mp, long long key) {
  auto it = mp.find(key);
  return it != mp.end() ? it->second : 0;
}
long long solve() {
  for (int i = (0); i < (alen); ++i) arev[alen - i - 1] = a[i];
  arev[alen] = '\0';
  for (int i = (0); i < (blen); ++i) brev[blen - i - 1] = b[i];
  brev[blen] = '\0';
  ta.init(a);
  ta.build();
  tb.init(b);
  tb.build();
  tarev.init(arev);
  tarev.build();
  tbrev.init(brev);
  tbrev.build();
  ha.init(a);
  ha.build();
  hb.init(b);
  hb.build();
  acnt.clear();
  bcnt.clear();
  asuff.clear();
  bpref.clear();
  long long ret = (long long)(ta.nnodes - 2) * (tb.nnodes - 2);
  for (int i = (2); i < (ta.nnodes); ++i) {
    int pl = ta.nodes[i].firststart,
        pr = ta.nodes[i].firststart + ta.nodes[i].len - 1;
    acnt[ha.get(pl, pr).val()]++;
    if (ta.nodes[i].suff < 2) continue;
    int vl = pl + ta.nodes[ta.nodes[i].suff].len, vr = pr;
    asuff[ha.get(vl, vr).val()]++;
  }
  for (int i = (2); i < (tb.nnodes); ++i) {
    int pl = tb.nodes[i].firststart,
        pr = tb.nodes[i].firststart + tb.nodes[i].len - 1;
    bcnt[hb.get(pl, pr).val()]++;
    if (tb.nodes[i].suff < 2) continue;
    int vl = pl, vr = pr - tb.nodes[tb.nodes[i].suff].len;
    bpref[hb.get(vl, vr).val()]++;
  }
  for (int i = (2); i < (ta.nnodes); ++i) {
    int pl = ta.nodes[i].firststart,
        pr = ta.nodes[i].firststart + ta.nodes[i].len - 1;
    if (ta.nodes[i].suff < 2) continue;
    int vl = pl + ta.nodes[ta.nodes[i].suff].len, vr = pr, xl = pl, xr = vl - 1;
    if (vr - vl <= xr - xl) ret -= safeget(bpref, ha.get(vl, vr).val());
    int wl, wr, yl, yr;
    if (decompose(ta, tarev, alen, vl, vr, yl, yr, wl, wr))
      ret -= safeget(bcnt, gettrihash(ha, yl, yr, wl, wr, yl, yr).val());
  }
  for (int i = (2); i < (tb.nnodes); ++i) {
    int pl = tb.nodes[i].firststart,
        pr = tb.nodes[i].firststart + tb.nodes[i].len - 1;
    if (tb.nodes[i].suff < 2) continue;
    int vl = pl, vr = pr - tb.nodes[tb.nodes[i].suff].len, xl = vr + 1, xr = pr;
    if (vr - vl <= xr - xl) ret -= safeget(asuff, hb.get(vl, vr).val());
    int wl, wr, yl, yr;
    if (decompose(tb, tbrev, blen, vl, vr, wl, wr, yl, yr))
      ret -= safeget(acnt, gettrihash(hb, yl, yr, wl, wr, yl, yr).val());
  }
  for (auto it = asuff.begin(); it != asuff.end(); ++it)
    ret += (long long)it->second * safeget(bpref, it->first);
  return ret;
}
void run() {
  scanf("%s", a);
  alen = strlen(a);
  scanf("%s", b);
  blen = strlen(b);
  printf("%lld\n", solve());
}
bool ispal(char *s, int i, int j) {
  while (i <= j) {
    if (s[i] != s[j]) return false;
    ++i, --j;
  }
  return true;
}
long long bfsolve() {
  set<string> apal;
  for (int i = (0); i < (alen); ++i)
    for (int j = (i); j < (alen); ++j)
      if (ispal(a, i, j)) apal.insert(string(a + i, a + j + 1));
  set<string> bpal;
  for (int i = (0); i < (blen); ++i)
    for (int j = (i); j < (blen); ++j)
      if (ispal(b, i, j)) bpal.insert(string(b + i, b + j + 1));
  set<string> ret;
  for (auto ait = apal.begin(); ait != apal.end(); ++ait)
    for (auto bit = bpal.begin(); bit != bpal.end(); ++bit)
      ret.insert(*ait + *bit);
  return ((int)(ret).size());
}
void stress1() {
  int t = 0;
  for (alen = 1; alen <= 10; ++alen)
    for (blen = 1; blen <= 10; ++blen)
      for (int amask = (0); amask < (1 << alen); ++amask)
        for (int bmask = (0); bmask < (1 << blen); ++bmask) {
          for (int i = (0); i < (alen); ++i)
            a[i] = (amask & (1 << i)) == 0 ? 'x' : 'y';
          a[alen] = '\0';
          for (int i = (0); i < (blen); ++i)
            b[i] = (bmask & (1 << i)) == 0 ? 'x' : 'y';
          b[blen] = '\0';
          long long have = solve();
          long long want = bfsolve();
          if (have == want) {
            if (++t % 1000 == 0) printf(".");
            continue;
          }
          printf("err a=%s b=%s have=%lld want=%lld\n", a, b, have, want);
          return;
        }
}
void stress2() {
  for (int rep = (0); rep < (10); ++rep) {
    alen = MAXLEN;
    for (int i = (0); i < (alen); ++i) a[i] = 'a' + rand() % 26;
    a[alen] = '\0';
    blen = MAXLEN;
    for (int i = (0); i < (blen); ++i) b[i] = 'a' + rand() % 26;
    b[blen] = '\0';
    long long have = solve();
    printf("%lld\n", have);
  }
}
int main() {
  run();
  return 0;
}

```