A palindrome is a string that reads the same forwards and backwards.
For example, "abba" and "racecar" are palindromes.
Limak has a String s consisting of N lowercase English letters.
For each valid i, let X[i] be the number of palidromic subsequences of s that contain the i-th character of s.
In other words:
For a fixed i, there are exactly 2^(N-1) ways to erase some characters of s other than the character s[i].
X[i] is the number of ways of erasing for which the string that remains is a palindrome.
For each i, compute the value Y[i] = ((i+1) * X[i]) modulo 1,000,000,007.
Then, compute and return the bitwise XOR of all the values Y[i]. |