Problem Statement

"suidousui" is a palindrome

Decompose a string $S$ into $k (\geq 1)$ non-empty substrings, and call them $ T_1, T_2, \dots , T_k $ in order from the beginning.
($ S = T_1 + T_2 + \dots + T_k $ , $ |T_i| \geq 1 $)
If $T_i = T_{k-i+1}$ holds for all $i (1 \leq i \leq k)$, the sequence $T( = [T_1,T_2,\dots,T_k] )$ is called a palindrome-kai decomposition of the string $S$.

Given a string $S$, compute the number of possible palindrome-kai decompositions.
Since the answer can be very large, output it modulo $1,000,000,007$.

Input

$S$

$S$ satisfies the following constraints.
$1 \leq |S| \leq 10^4$
$S$ consists only of lowercase letters 'a' - 'z'

Output

Output the number of possible palindrome-kai decompositions, modulo $1,000,000,007$.

Sample

abc

1

suidousui

2

kaibunkaibunkai

3

aaaaa

4