G. 回文划分

时间限制：每个测试点 3 秒
内存限制：256 MB

给定一个字符串 $s$，求将其分割成若干子串的方式数，使得若分割后有 $k$ 个子串 $(p_1, p_2, p_3, \dots, p_k)$，则对所有 $i\ (1 \le i \le k)$ 满足 $p_i = p_{k-i+1}$，且 $k$ 为偶数。

由于方案数可能很大，请输出它对 $10^9+7$ 取模的结果。

输入
仅一行，包含一个字符串 $s$（$2 \le |s| \le 10^6$），长度为偶数，由小写拉丁字母组成。

输出
输出一个整数，表示满足条件的分割方案数对 $10^9+7$ 取模的结果。

样例

输入

abcdcdab

输出

1

输入

abbababababbab

输出

3

说明
在第一个样例中，唯一的分割方式为：
$ab\ |\ cd\ |\ cd\ |\ ab$。

在第二个样例中，字符串可以分割为：
$ab\ |\ b\ |\ ab\ |\ ab\ |\ ab\ |\ ab\ |\ b\ |\ ab$
或
$ab\ |\ b\ |\ abab\ |\ abab\ |\ b\ |\ ab$
或
$abbab\ |\ ab\ |\ ab\ |\ abbab$。