题目描述

给定 $ 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 $ 取模后的结果。

样例

input

2
bbbaa
bb

output

30

数据范围与提示

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