Palindrome Partition

题号：NC236739
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

The only line of input contains a string  of even length consisting of lowercase Latin letters.

输出描述:

Print one integer, the number of ways of partitioning the string modulo .

示例1

输入

复制

abcdcdab

输出

复制

示例2

输入

复制

abbababababbab

输出

复制

备注:

https://codeforces.com/contest/932/problem/G