红牛的老师听说红牛学会了循环移位,决定给他出下面的题。
给定一个包含列表 A 中包含的 n 个字符串 s1, s2, ..., sn 的列表。
如果满足以下条件,则字符串列表 X 被称为稳定的。
首先,消息被定义为列表 X 的某些元素的串联。您可以根据需要多次使用任意元素,并且可以以任意顺序串联这些元素。让 SX 表示您可以从列表中构造的所有消息的集合。当然,如果您的列表非空,则该集合具有无限大小。
如果满足以下条件,则称单个消息良好:
- 假设消息是 k 个字符串 w1, w2, ..., wk 的串联,其中每个 wi 是 X 的一个元素。
- 考虑 |w1| + |w2| + ... + |周|字符串的循环移位。令 m 为作为 SX 元素的字符串的这些循环移位的数量。
- 当且仅当 m 完全等于 k 时,消息才是好的。
列表 X 被称为稳定当且仅当 SX 的每个元素都是好的。
如果 L 是稳定列表,则令 f(L) 为 1,否则为 0。
求 f(L) 的和,其中 L 是 A 的非空连续子列表(总共有 $$\frac{n(n+1)}{2}$$ 连续子列表)。
输入
输入的第一行将包含一个整数 n (1 ≤ n ≤ 30),表示列表中字符串的数量。
接下来的 n 行将分别包含一个字符串 si ($$1 \leq | s _ { i } |, \sum _ { i = 1 } ^ { n } | s _ { i } | \leq 100 \, 000$$)。
输出
打印单个整数,即稳定的非空连续子列表的数量。
示例
输入 #1
4 a ab b bba
输出 #1
7
输入 #2
5 hh ee ll ll oo
输出 #2
0
输入 #3
6 aab ab bba b ab c
输出 #3
13
注意
对于第一个示例,需要考虑 10 个子列表。子列表 ["a", "ab", "b"]、["ab", "b", "bba"] 和 ["a", "ab", "b", "bba"] 不稳定。其他七个子列表稳定。
例如,X = ["a", "ab", "b"] 是不稳定的,因为消息 "ab" + "ab" = "abab" 有四个循环移位 ["abab", "baba", "abab", "baba"],它们都是 SX 的元素。