无限链计数

【题目描述】

你可以用前$t$个小写字母来组成两段都无限长的链，要求这些链中不能出现$n$个给定的串中的任何一个，请问有多少个满足条件的不同的无限链呢？两个相同的两端均无限长的链$A$和$B$需要满足的条件为$A[i+k]=B[i]$对于任意的$i$都成立，其中$k$为任意整数。 例如$t=2$，给定串为$\{ab,ba\}$，那么只有$…aaa…$与$…bbb…$两个，如果给定串为$\{ab\}$，则有$…aaa…,…bbb…,…bbbbaaa…$三个。

【输入】

第一行两个整数$t$和$n$，含义如题所述。 接下来$n$行每行一个字符串表示一个不能出现的串。

【输出】

输出一行一个整数表示答案，如果有无限多个输出$-1$，保证答案不超过$2^{31}-1$。

【输入样例】

2 2
ab
ba

【输出样例】

2

【提示】

【数据规模与约定】 对于20%的数据，$t≤2，n=1$； 对于另外30%的数据，$t≤2$； 对于100%的数据，$n≤1000，t≤6$，每个给定的串长度不超过$10$。