题目描述

有一种特殊的集合叫做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$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。