Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.
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.