#6071. 「2017 山东一轮集训 Day5」字符串

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定 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