#1803. 「NOI2014」动物园

「NOI2014」动物园

题目描述

近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决定开设算法班,让动物们学习算法。

某天,园长给动物们讲解KMP算法。
园长:「对于一个字符串 SS,它的长度为 LL。我们可以在 O(L)O(L) 的时间内,求出一个名为 next\textrm{next} 的数组。有谁预习了 next\textrm{next} 数组的含义吗?」
熊猫:「对于字符串 SS 的前 ii 个字符构成的子串,既是它的后缀又是它的前缀的字符串中(它本身除外),最长的长度记作 nexti\textrm{next}_i。」
园长:「非常好!那你能举个例子吗?」
熊猫:「例如 SS 若为 abcababc,则 next5=2\textrm{next}_5=2。因为 SS 的前五个字符为 abcabab 既是它的后缀又是它的前缀,并且找不到一个更长的字符串满足这个性质。同理,还可得出 $\textrm{next}_1 =\textrm{next}_2 = \textrm{next}_3 = 0,\ \textrm{next}_4 = \textrm{next}_6 = 1,\ \textrm{next}_7 = 2,\ \textrm{next}_8 = 3$。」

园长表扬了认真预习的熊猫同学。随后,他详细讲解了如何在 O(L)O(L) 的时间内求出 next\textrm{next} 数组。

下课前,园长提出了一个问题:「KMP 算法只能求出 next\textrm{next} 数组。我现在希望求出一个更强大 num\textrm{num} 数组一一对于字符串 SS 的前 ii 个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作 numi\textrm{num}_i。例如 SSaaaaa,则 num4=2\textrm{num}_4 = 2。这是因为 SS 的前四个字符为 aaaa,其中 aaa 都满足性质『既是后缀又是前缀』,同时保证这个后缀与这个前缀不重叠。而 aaa 虽然满足性质『既是后缀又是前缀』,但遗憾的是这个后缀与这个前缀重叠了,所以不能计算在内。同理,$\textrm{num}_1 = 0,\ \textrm{num}_2 = \textrm{num}_3 = 1,\ \textrm{num}_5 = 2$。」

最后,园长给出了奖励条件,第一个做对的同学奖励巧克力一盒。听了这句话,睡了一节课的企鹅立刻就醒过来了!但企鹅并不会做这道题,于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出 num\textrm{num} 数组呢?

特别地,为了避免大量的输出,你不需要输出 numi\textrm{num}_i 分别是多少,你只需要输出 i=1L(numi+1)\prod_{i=1}^L (\textrm{num}_i+1)1,000,000,0071,000,000,007 取模的结果即可。

输入格式

第一行仅包含一个正整数 nn ,表示测试数据的组数。
随后 nn 行,每行描述一组测试数据。
每组测试数据仅含有一个字符串 SSSS 的定义详见题目描述。数据保证 SS 中仅含小写字母。输入文件中不会包含多余的空行,行末不会存在多余的空格。

输出格式

包含 nn 行,每行描述一组测试数据的答案,答案的顺序应与输入数据的顺序保持一致。
对于每组测试数据,仅需要输出一个整数,表示这组测试数据的答案对 1,000,000,0071,000,000,007 取模的结果。输出文件中不应包含多余的空行。

样例

3
aaaaa
ab
abcababc
36
1
32

数据范围与提示

对于所有数据,n5,L106n \leq 5,L \leq 10^6

测试点编号 约定
11 n5,L50n\le 5,L\le 50
22 n5,L200n\le 5,L\le 200
33
44 n5,L10000n\le 5,L\le 10000
55
66 n5,L100000n\le 5,L\le 100000
77 n5,L200000n\le 5,L\le 200000
88 n5,L500000n\le 5,L\le 500000
99 n5,L1000000n\le 5,L\le 1000000
1010