题目描述

你可以用前$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$。

评测数据说明

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