czq获得了一个长为的字符串,他可以把这个字符串划分成两个部分并分别将其按照原顺序组成字符串,如果是回文串,那么称他成功破解了回文密码。
例如为abbcca,则令为第1,2,4,5个字符组成的字符串abcc,则为ba,为abccba是回文串。
abbcca
abcc
ba
abccba
回文串指正读和反读都一样的字符串。
请问有多少可能的划分,使得czq能破解回文密码?
第一行一个整数。
第二行一个字符串,长为。
仅一个整数为答案。
2 abba
8
5 aabdcbcdaa
48
18 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
68719476736
保证字符串仅由小写英文字符组成。