#P932G. Palindrome Partition
-
ID: 4170
Type: RemoteJudge
3000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Palindrome Partition
No submission language available for this problem.
Description
Given a string s, find the number of ways to split s to substrings such that if there are k substrings (p1, p2, p3, ..., pk) in partition, then pi = pk - i + 1 for all i (1 ≤ i ≤ k) and k is even.
Since the number of ways can be large, print it modulo 109 + 7.
The only line of input contains a string s (2 ≤ |s| ≤ 106) of even length consisting of lowercase Latin letters.
Print one integer, the number of ways of partitioning the string modulo 109 + 7.
Input
The only line of input contains a string s (2 ≤ |s| ≤ 106) of even length consisting of lowercase Latin letters.
Output
Print one integer, the number of ways of partitioning the string modulo 109 + 7.
Samples
abcdcdab
1
abbababababbab
3
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.