409149: GYM103447 A So Many Lucky Strings

The first man was called George. He likes to play string concatenating games. He has a sequence $$$\{s_1,s_2,...s_n\}$$$ which is composed of $$$n$$$ strings. Sometimes he selects some strings from the sequence and concatenate them together in their original relative order to form a string. It means that he can arbitrarily choose a sequence of integer $$$A=\{a_1,a_2,..,a_k\},\ (1\le k \le n,\ 1\le a_1<a_2<...<a_k\le n)$$$ , and then he will concatenate $$$s_{a_1},s_{a_2},\cdots,s_{a_k}$$$ together to form a new string $$$s_{a_1}+s_{a_2}+...+s_{a_k}$$$, where $$$S+T$$$ means to put string $$$T$$$ right after string $$$S$$$. For example, if his string sequence is $$$\{\text{heh},\text{e},\text{j},\text{ie}\}$$$ and he chooses $$$\{1,3,4\}$$$ ,then he will get a string "$$$\text{hehjie}$$$".

The second man is called Karsh. He likes lucky strings. If a string is the same as itself after reversion, Karsh calls it a lucky string (or palindrome string).

Today day Karsh meets George. He hopes George could choose such a sequence $$$A$$$, concatenate the strings according to the chosen sequence, and finally form a lucky string for him.

Then the problem comes. How many different choices are there to form a lucky string?

The first line contains an integer $$$n\,(1\le n\le 100)$$$, denoting the number of George's strings.

Following $$$n$$$ lines each contains a string $$$s_i\,(1\le |s_i|\le 10^5)$$$, denoting the string sequence.

It is guaranteed that $$$\sum|s_i| \le 10^5$$$ , and that all the strings only contain lower-case letters.

Output one line containing an integer, denoting the number of different sequence choices to make a lucky string. Since the answer may be too large, you should output it modulo $$$1000000007$$$.

4
a
b
aba
a

8

6
hehe
he
he
eh
he
jie

3

For the first case, there are $$$8$$$ different sequence choices to form a lucky string: $$$\{1\}$$$, $$$\{2\}$$$, $$$\{3\}$$$, $$$\{4\}$$$, $$$\{1,4\}$$$, $$$\{1,2,4\}$$$, $$$\{1,3,4\}$$$, $$$\{1,2,3\}$$$.