H. Палиндромная магия
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

После изучения всяких разных палиндромовых алгоритмов, Chouti решил, что палиндромы это очень интересно, и он решил дать вам следующую задачу.

У Chouti есть две строки $$$A$$$ и $$$B$$$. Так как он любит палиндромы, он хочет выбрать $$$a$$$ как непустую палиндромную подстроку строки $$$A$$$, а $$$b$$$ как непустую палиндромную подстроку строки $$$B$$$. Сконкатенировав их, он получит строку $$$ab$$$.

Chouti считает, что строки, которые можно получить таким образом, очень интересные, поэтому он хочет знать, скоько различных строк он может так получить.

Входные данные

Первая строка содержит одну строка $$$A$$$ ($$$1 \le |A| \le 2 \cdot 10^5$$$).

Вторая строка содержит одну строка $$$B$$$ ($$$1 \le |B| \le 2 \cdot 10^5$$$).

Строки $$$A$$$ и $$$B$$$ состоят только из строчных английских букв.

Выходные данные

В единственной строка выведите одно целое число — количество возможных строк.

Примеры
Входные данные
aa
aba
Выходные данные
6
Входные данные
aaba
abaa
Выходные данные
15
Примечание

В первом примере можно получить строки

  • "a" + "a" = "aa",
  • "aa" + "a" = "aaa",
  • "aa" + "aba" = "aaaba",
  • "aa" + "b" = "aab",
  • "a" + "aba" = "aaba",
  • "a" + "b" = "ab".

Во втором примере можно получить строки "aa", "aaa", "aaaa", "aaaba", "aab", "aaba", "ab", "abaa", "abaaa", "abaaba", "abab", "ba", "baa", "baba", "bb".

Обратите внимание, что, не смотря на то, что "a"+"aa"="aa"+"a"="aaa", строка "aaa" учитывается только один раз.