Interesting

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

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.

Input

The input contains multiple test cases.

Each test case contains one string. The length of string is between 1 and 1000000. String only contains lowercase letter.

Output

For each test case output the answer mod 1000000007.

Sample Input

aaa abc

Sample Output

14 8

Hint

wange2014

Source

2016 Multi-University Training Contest 5

提交代码