markdown 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
  共 $3$ 种方案。