Problem: Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's practice is to improve the ability to read messages hidden from sentences by searching for palindromes in strings. There may be many palindromes, so I'd like to count the number while searching.

Given two strings S and T, we want to find the number of pairs of integers (i, j, k, l) that satisfy the following:

* 1 ≤ i ≤ j ≤ (length of S).
* 1 ≤ k ≤ l ≤ (length of T).
* The substrings extracted from the i-th to j-th characters of S are the same as the substrings extracted from the k-th to l-th characters of T, and these are palindromes (even when read from the left). It is a character string that is the same even when read from the right).



Input


S
T


Both the strings S and T have a length of 1 or more and 50,000 or less, and consist of uppercase letters.

Output

Output the number of pairs of integers (i, j, k, l) that satisfy the condition on one line.

Examples

Input

ICPC
CPCPC


Output

10


Input

BABBAB
ABBA


Output

14


Input

MYON
USAGI


Output

0

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())
#define ten(n) ((int)1e##n)
using ll = long long;

template<typename ...> static inline int getchar_unlocked(void) { return getchar(); }
template<typename ...> static inline void putchar_unlocked(int c) { putchar(c); }
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
void reader(ll& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
int reader(string& c) { int i; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c.push_back(i); for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c.push_back(i); }; return sz(c); }
template <class T, class S> void reader(T& x, S& y) { reader(x); reader(y); }
template <class T, class S, class U> void reader(T& x, S& y, U& z) { reader(x); reader(y); reader(z); }
template <class T, class S, class U, class V> void reader(T& x, S& y, U& z, V & w) { reader(x); reader(y); reader(z); reader(w); }
void writer(int x, char c) { int s = 0, m = 0; char f[10]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(ll x, char c) { int s = 0, m = 0; char f[20]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(const char c[]) { int i; for (i = 0; c[i] != '\0'; i++)mypc(c[i]); }
void writer(const char x[], char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
template<class T> void writerLn(T x) { writer(x, '\n'); }
template<class T, class S> void writerLn(T x, S y) { writer(x, ' '); writer(y, '\n'); }
template<class T, class S, class U> void writerLn(T x, S y, U z) { writer(x, ' '); writer(y, ' '); writer(z, '\n'); }
template<class T> void writerArr(T x[], int n) { if (!n) { mypc('\n'); return; }FOR(i, n - 1)writer(x[i], ' '); writer(x[n - 1], '\n'); }
template<class T> void writerArr(vector<T>& x) { writerArr(x.data(), (int)x.size()); }

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
ll mod_pow(ll a, ll n, ll mod) {
	ll ret = 1;
	ll p = a % mod;
	while (n) {
		if (n & 1) ret = ret * p % mod;
		p = p * p % mod;
		n >>= 1;
	}
	return ret;
}
template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; }
template<class T> T mod_inv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; }

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

struct PalindromicTree {
// private:
	struct node {
		map<char, int> link;
		int suffix_link;
		int len;
		int depth;
	};
	
	vector<node> c;
	string s;
	int max_suffix_palindrome_idx;

	node* create_node() {
		c.emplace_back();
		node* ret = &c.back();
		return ret;
	}

	// depends on "string s"
	int find_prev_palindrome_idx(int node_id) {
		const int pos = sz(s) - 1;
		while (true) {
			const int opposite_side_idx = pos - 1 - c[node_id].len;
			if (opposite_side_idx >= 0 && s[opposite_side_idx] == s.back()) break;
			node_id = c[node_id].suffix_link; // climb suffix link up
		}
		return node_id;
	}

public:
	PalindromicTree() {
		node* size_m1 = create_node(); // create size = -1 node
		size_m1->suffix_link = 0; // link to size_m1
		size_m1->len = -1;
		size_m1->depth = 0;
		node* size_0 = create_node(); // create size = 0 node
		size_0->suffix_link = 0; // link to size_m1
		size_0->len = 0;
		size_0->depth = 0;

		max_suffix_palindrome_idx = 0;
	}

	int get_max_suffix_palindrome_idx() const {
		return max_suffix_palindrome_idx;
	}
	node* get_node(int id) {
		return &c[id];
	}

	void add(char ch) {
		s.push_back(ch);

		// ch + [A] + ch is palindrome
		const int a = find_prev_palindrome_idx(max_suffix_palindrome_idx);

		const auto inserted_result = c[a].link.insert(make_pair(ch, -1)); //"-1" means dummy data
		if (!inserted_result.second) {
			max_suffix_palindrome_idx = inserted_result.first->second;
			return; // found same palindrome
		}

		max_suffix_palindrome_idx = inserted_result.first->second = sz(c); // replace dummy data to actual one
		
		// create new entry
		node* nnode = create_node();
		nnode->len = c[a].len + 2;
		
		// update suffix_link
		if (nnode->len == 1) {
			nnode->suffix_link = 1; // link to size_0
		} else {
			// ch + [B] + ch is also palindrome
			const int b = find_prev_palindrome_idx(c[a].suffix_link);
			nnode->suffix_link = c[b].link[ch];
		}
		nnode->depth = c[nnode->suffix_link].depth + 1;
	}
};

vector<ll> calc_dp(PalindromicTree& pt, vector<int>& cnt) {
	vector<ll> ret(sz(pt.c));
	for (int v = sz(pt.c) - 1; v > 0; v--) {
		ret[v] += cnt[v];
		ret[pt.c[v].suffix_link] += ret[v];
	}
	ret[0] = ret[1] = 0;
	for(int v = 2; v < sz(pt.c); v++) {
		ret[v] += ret[pt.c[v].suffix_link];
	}
	return ret;
}

int main() {
	string s, t; reader(s, t);

	vector<int> cnt(sz(s) + sz(t) + 10);
	vector<int> cnt2(sz(s) + sz(t) + 10);
	PalindromicTree pt;
	for (auto c : s) {
		pt.add(c);
		cnt[pt.get_max_suffix_palindrome_idx()]++;
	}

	pt.add('!');
	pt.add('"');
	for (auto c : t) {
		pt.add(c);
		cnt2[pt.get_max_suffix_palindrome_idx()]++;
	}

	auto dp = calc_dp(pt, cnt);
	ll ans = 0;
	FOR(i, sz(dp)) {
		ans += dp[i] * cnt2[i];
	}

	writerLn(ans);
}