题目描述

给定 $n$ 个字符集为小写字母的字符串 $s_i$，一个串 $t$ 是可接受的，当且仅当 $t$ 可以表示成 $p_1 + p_2 + \cdots + p_n$，其中 $p_i$ 为 $s_i$ 的一个子串（可以为空），$+$ 表示字符串的拼接。问有多少种本质不同的字符串 $t$ 是可接受的。答案对 $10 ^ 9 + 7$ 取模。

输入格式

第一行一个整数 $n$。
接下来 $n$ 行，每行一个字符串 $s_i$。

输出格式

输出一行一个整数，表示可接受的字符串的数目对 $10 ^ 9 + 7$ 取模后的结果。

2
bbbaa
bb

30

数据范围与提示

第 1、2 个测试点，满足 $n \leq 5, |s_i| \leq 7$；
第 3 个测试点，满足 $n = 1$；
第 4 个测试点，满足 $n = 2$；
第 5、6 个测试点，满足 $\sum\limits_{i = 1} ^ n |s_i| \leq 1000$；
第 7、8、9、10 个测试点，满足 $ n \leq 10 ^ 6; \sum\limits_{i = 1} ^ n |s_i| \leq 10 ^ 6 $。