G. Palindrome Partition
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a string s, find the number of ways to split s to substrings such that if there are k substrings (p1, p2, p3, ..., pk) in partition, then pi = pk - i + 1 for all i (1 ≤ i ≤ k) and k is even.

Since the number of ways can be large, print it modulo 109 + 7.

Input

The only line of input contains a string s (2 ≤ |s| ≤ 106) of even length consisting of lowercase Latin letters.

Output

Print one integer, the number of ways of partitioning the string modulo 109 + 7.

Examples
Input
abcdcdab
Output
1
Input
abbababababbab
Output
3
Note

In the first case, the only way to partition the string is ab|cd|cd|ab.

In the second case, the string can be partitioned as ab|b|ab|ab|ab|ab|b|ab or ab|b|abab|abab|b|ab or abbab|ab|ab|abbab.