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}。