import sys from collections import defaultdict sys.setrecursionlimit(int(1e7)) MOD = (1<<61) - 1 BASE = 998244353 MAXN = 5 * 10**5 POWER = [1] for i in range(1, MAXN+1): POWER.append((POWER[-1] * BASE) % MOD) class RollingHash: def __init__(self, string): self.string = string self.size = len(string) # construct self.hashed = [0] for i in range(self.size): self.hashed.append(self.hashed[-1] * BASE + ord(self.string[i])) self.hashed[-1] %= MOD def query(self, l, r): assert 0 <= l <= r <= self.size return (self.hashed[r] - self.hashed[l] * POWER[r-l]) % MOD def composite_query(R1, R2, l1, r1, l2, r2): LEFT = R1.query(l1, r1) RIGHT = R2.query(l2, r2) return (RIGHT + LEFT * POWER[r2-l2]) % MOD class eertree: def __init__(self, string): self.string = string self.size = len(string) self.r1 = RollingHash(self.string) self.r2 = RollingHash(''.join(reversed(self.string))) def __rev(self, l, r): return self.size - r, self.size - l def build(self): BEGIN = ord('A') # or ord('a') # Centroid of the palindrome A-Z and '' PALINDROME_SIZE = 2 * self.size G = [[] for _ in range(PALINDROME_SIZE)] H = [0] * PALINDROME_SIZE W = [0] * PALINDROME_SIZE ptr = [defaultdict(lambda: -1) for _ in range(27)] ptr[26][0] = 0 H[0] = (26, 0) free = 1 for i in range(self.size): # Centroid = self.string[i] ok, ng = -1, min(i, self.size-i-1)+1 ID = ord(self.string[i]) - BEGIN while ng - ok > 1: x = (ng + ok) >> 1 h1 = self.r1.query(i+1, i+1+x) # [i+1, i+1+x) h2 = self.r2.query(self.size-i, self.size-i+x) # [i-x, i) if ptr[ID][h1] >= 0 and h1 == h2: ok = x else: ng = x if ok == -1: ptr[ID][0] = free H[free] = (ID, 0) free += 1 ok = 0 par = ptr[ID][self.r1.query(i+1,i+1+ok)] for j in range(ok+1, min(i+1, self.size-i)): c1 = self.string[i+j] c2 = self.string[i-j] if c1 == c2: h1 = self.r1.query(i+1, i+j+1) ptr[ID][h1] = free G[par].append(free) H[free] = (ID, h1) par = free free += 1 else: break W[par] += 1 # Centroid = '' ok, ng = 0, min(i, self.size-i-1) + 1 ID = 26 while ng - ok > 1: x = (ng + ok) >> 1 h1 = self.r1.query(i, i+x) # [i, i+x) h2 = self.r2.query(self.size-i, self.size-i+x) # [i-x, i) if ptr[ID][h1] >= 0 and h1 == h2: ok = x else: ng = x par = ptr[ID][self.r1.query(i,i+ok)] for j in range(ok+1, min(i+1, self.size-i+1)): c1 = self.string[i+j-1] c2 = self.string[i-j] if c1 == c2: h1 = self.r1.query(i, i+j) ptr[ID][h1] = free G[par].append(free) H[free] = (ID, h1) par = free free += 1 else: break W[par] += 1 def dfs(v): for nxt in G[v]: W[v] += dfs(nxt) return W[v] for ID in range(27): if ptr[ID][0] >= 0: dfs(ptr[ID][0]) W[0] = 0 return W, H s = input() t = input() palS = eertree(s) palT = eertree(t) SW, SH = palS.build() TW, TH = palT.build() pair = defaultdict(lambda: [0, 0]) for i in range(len(SW)): pair[SH[i]][0] += SW[i] for i in range(len(TW)): pair[TH[i]][1] += TW[i] ans = 0 for key in pair.keys(): x, y = pair[key] ans += x * y print(ans)