Assume that the strings s and t of length n are equivalent, if, for each pair of indices i and j such that 1 \le i \le j \le n, a substring of s consisting of symbols from i-th to j-th is a palindrome if and only if the substring of t consisting of symbols from i-th to j-th is also a palindrome (if the corresponding substring of s is not a palindrome then the substring of t will not be a palindrome as well).
Given the string s, find the number of strings that are equivalent to s and have the same length.
You are allowed to use any lowercase letters of the English alphabet.
Input
A single line contains a non-empty string s. The string length does not exceed 10^6.
Output
Output a single number, the answer to the problem modulo 1\,000\,000\,007.
Examples
| standard input | standard output |
|---|
| icpc
| 15600
|
| abacaba
| 15600
|
| yxxy
| 650
|