So Many Lucky Strings(https://acs.jxnu.edu.cn/problem/GYM103447A)

2022寒假翻译12

这么多幸运的字符串
1000 ms 524288 k
描述:
第一个人叫乔治。他喜欢玩串线游戏。他有一个序列{s1,s2,…Sn}由n个字符串组成。有时,他从序列中选择一些字符串,并将它们按照最初的相对顺序连接在一起,形成一个字符串。这意味着他可以任意选择一个整数序列a ={a1,a2,..,ak},(1≤k≤n, 1≤a1<a2<…< an>例如,如果他的字符串序列是{heh,e,j,ie},他选择{1,3,4},那么他将得到一个字符串“hehjie”。

第二个人叫卡什。他喜欢幸运线。如果一个字符串在回归后和它本身一样,卡什称它为幸运字符串(或回文字符串)。

今天卡什遇见了乔治。他希望George能够选择这样一个序列a,并将选中的序列串起来,最终形成一个幸运的字符串。

然后问题就来了。有多少种不同的选择可以组成一个幸运的字符串?

输入:
第一行包含一个整数n(1≤n≤100),表示George的字符串的数量。

每n行后面包含一个字符串si(1≤|si|≤105),表示字符串序列。

保证∑|si|≤105,且所有字符串只包含小写字母。

输出:
输出一行包含一个整数,表示要组成一个幸运字符串需要选择的不同序列的数量。由于答案可能太大,您应该输出对1000000007取模的结果。

样例输入:

4
a
b
aba
a

样例输出:

8

样例输入:

6
hehe
he
he
eh
he
jie

样例输出:

3


注释:
对于第一种情况,有8种不同的序列选择来组成一个幸运字符串:{1},{2},{3},{4},{1,4},{1,2,4},{1,3,4},{1,2,3}。

上一篇:IMX6ULL学习踩坑笔记1——Bad Linux ARM zImage magic


下一篇:JXNU 月考题--面积与周长关系问题