Given a string $*s*$, find the number of ways to split $*s*$ to substrings such that if there are $*k*$ substrings $(*p*_{1}, *p*_{2}, *p*_{3}, ..., *p*_{*k*})$ in partition, then $*p*_{*i*} = *p*_{*k* - *i* + 1}$ for all $*i*$ $(1 ≤ *i* ≤ *k*)$ and $*k*$ is even.

Since the number of ways can be large, print it modulo $10^{9} + 7$.

Input

The only line of input contains a string $*s*$ $(2 ≤ |*s*| ≤ 10^{6})$ of even length consisting of lowercase Latin letters.

Output

Print one integer, the number of ways of partitioning the string modulo $10^{9} + 7$.

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*$.