Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

string suffix structures

strings

*2900

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Palindrome Partition

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputGiven 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.

Input

The only line of input contains a string *s* (2 ≤ |*s*| ≤ 10^{6}) of even length consisting of lowercase Latin letters.

Output

Print one integer, the number of ways of partitioning the string modulo 10^{9} + 7.

Examples

Input

abcdcdab

Output

1

Input

abbababababbab

Output

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/06/2023 02:54:15 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|