Palindrome Partition

3000ms

262144K

Description:

Given a string s, find the number of ways to split s to substrings such that if there are k substrings (p₁, p₂, p₃, ..., 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⁹ + 7.

Input:

The only line of input contains a string s (2 ≤ |s| ≤ 10⁶) of even length consisting of lowercase Latin letters.

Output:

Print one integer, the number of ways of partitioning the string modulo 10⁹ + 7.

Sample Input:

abcdcdab

Sample Output:

Sample Input:

abbababababbab

Sample Output:

Note:

In the first case, the only way to partition the string is ab|cd|cd|ab.

In the second case, the string can be partitioned as ab|b|ab|ab|ab|ab|b|ab or ab|b|abab|abab|b|ab or abbab|ab|ab|abbab.

Informação

Provedor Codeforces

Código CF932G