友情提示:380元/半年,儿童学编程,就上码丁实验室。
【题目描述】
有一种特殊的集合叫做PFS(Prefix Free Set)集合。
一个PFS集合由若干字符串构成,且不存在一个字符串是另一个字符串的前缀。空集也被看作是PFS集合。
例如 {“$hello$”} 和 {“$hello$”, “$goodbye$”, “$giant$”, “$hi$”} 是PFS集合,但 {“$hello$”,”$hell$”} 和{“$great$”,”$gig$”,”$g$”} 不是。
现在给你一个集合,请你求出它的子集是PFS集合的子集个数,答案对$9191$取模。
【输入】
输入数据第一行一个整数$n$,表示集合里元素的个数。
以下$n$行,每行一个非空字符串$s$,仅包含小写英文字母,表示集合中的元素。数据保证不存在两个相同的字符串。
【输出】
输出一个正整数$ans$,表示对$9191$取模后的答案。
【输入样例】
3 hello hi hell
【输出样例】
6
【提示】
【输入输出样例解释】
除了 {“$hell$”,”$hello$”} 和 {“$hi$”,”$hello$”,”$hell$”} 两种情况外,其余情况均是PFS集合。
【数据规模】
对于30%的数据,$n≤20$;
对于100%的数据,$1≤n≤50000$,字符串长度不大于$50$。