CF932G.Palindrome Partition

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 109 + 7.

给定一个字符串 $s$，求将 $s$ 分割为若干子串的方法数，使得若分割后得到 $k$ 个子串（记为 $p_1,\,p_2,\,p_3,\,\dots,\,p_k$），则对所有 $i$（$1\le i\le k$）均满足 $p_i = p_{k-i+1}$，且 $k$ 为偶数。

由于方法数可能很大，请输出结果对 $10^9 + 7$ 取模的值。

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

输入仅包含一行，是一个长度为偶数的字符串 $s$（$2 \leq |s| \leq 10^6$），由小写拉丁字母组成。

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

输出一个整数，表示将该字符串划分的方式数目对 $10^9 + 7$ 取模的结果。

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.

在第一种情况下，该字符串唯一的划分方式是 ab|cd|cd|ab。

在第二种情况下，该字符串可以划分为 ab|b|ab|ab|ab|ab|b|ab，或 ab|b|abab|abab|b|ab，或 abbab|ab|ab|abbab。