← 返回题目列表

Codeforces · 932/G

G. 回文分区

中文机器翻译题面 查看原题

给定一个字符串 s,找到将 s 拆分为子字符串的方法数量,使得如果分区中有 k 个子字符串 (p1, p2, p3, ..., pk),则对于所有 i (1 ≤ i ≤ k),pi = pk - i + 1 并且 k 是偶数。

由于路数可能很大,因此将其打印为 109 + 7 模。

输入

输入的唯一一行包含由小写拉丁字母组成的偶数长度字符串 s (2 ≤ |s| ≤ 106)。

输出

打印一个整数,即以 109 + 7 为模的字符串划分方式的数量。

示例

输入 #1

abcdcdab

输出 #1

1

输入 #2

abbababababbab

输出 #2

3

注意

在第一种情况下,对字符串进行分区的唯一方法是 ab|cd|cd|ab。

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