回文式分割

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个字符串 $s$。你需要把它分割成偶数个非空连续子串 $(p_1,p_2,\ldots,p_k)$，并满足

求满足条件的分割方案数，答案对 $10^9+7$ 取模。两个方案只要存在一个切分位置不同，就视为不同方案。

输入格式

输入仅一行一个字符串 $s$。保证 $s$ 的长度为偶数，且只包含小写拉丁字母。

输出格式

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

样例输入 1

abcdcdab

样例输出 1

1

样例输入 2

abbababababbab

样例输出 2

3

数据范围

记 $n$ 为字符串长度。对于所有数据，$2\le n\le10^6$，$n$ 为偶数。