Будем считать, что строки s и t длины n эквивалентны, если для каждой пары индексов i и j таких, что 1 \le i \le j \le n, подстрока строки s, состоящая из символов с i-го по j-й, является палиндромом тогда и только тогда, когда подстрока строки t, состоящая из символов с i-го по j-й, является палиндромом (если соответствующая подстрока строки s не является палиндромом, то и в строке t она не будет являться палиндромом тоже).
Для заданной строки s необходимо найти количество строк, которые будут ей эквивалентны и иметь такую же длину, как и строка s.
Разрешается использовать все маленькие буквы английского алфавита.
Input
Единственная строка содержит непустую строку s. Гарантируется, что длина строки не превосходит 10^6.
Output
Выведите одно число — ответ на задачу по модулю 1\,000\,000\,007.
Examples
| standard input | standard output |
|---|
| icpc
| 15600
|
| abacaba
| 15600
|
| yxxy
| 650
|