После изучения всяких разных палиндромовых алгоритмов, Chouti решил, что палиндромы это очень интересно, и он решил дать вам следующую задачу.
У Chouti есть две строки \(A\) и \(B\). Так как он любит палиндромы, он хочет выбрать \(a\) как непустую палиндромную подстроку строки \(A\), а \(b\) как непустую палиндромную подстроку строки \(B\). Сконкатенировав их, он получит строку \(ab\).
Chouti считает, что строки, которые можно получить таким образом, очень интересные, поэтому он хочет знать, скоько различных строк он может так получить.
Выходные данные
В единственной строка выведите одно целое число — количество возможных строк.
Примечание
В первом примере можно получить строки
- "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" учитывается только один раз.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
aa
aba
|
6
|
|
2
|
aaba
abaa
|
15
|