Alice get a string S. She thinks palindrome string is interesting. Now she wanna know how many three tuple (i,j,k) satisfy $1\leq i\leq j<k\leq length(S)$, S[i..j] and S[j+1..k] are all palindrome strings. It's easy for her. She wants to know the sum of i*k of all required three tuples. She can't solve it. So can you help her? The answer may be very large, please output the answer mod 1000000007.
A palindrome string is a string that is same when the string is read from left to right as when the string is read from right to left.