测试数据来自 system/1853

描述

为了迎接2014，FSF拿到了n种彩带（每种彩带的数量为评测机的RP值），它们上面只含有”2“，”0“，”1“，”4“这四种数字，第i种彩带的长度为LR[i]。FSF想知道这些彩带一共能拼接成多少种长度为L的彩带（彩带可以重叠，但是重叠的部分必须相同）。
让我们形式化的定义一个正确拼接的彩带，设这条彩带为T，已有的彩带集合为S。若对于每一个1<=i<=L，都有T[l…l+LR[j]-1]=Sj，则称T是一条正确拼接的彩带。
现在给定彩带集合S和长度L，求所有可能的拼接后的彩带T的方案数对10^9+9取模后的结果。

格式

输入格式

第一行是两个正整数L和n(1 ≤ L ≤ 1000, 1 ≤ n ≤ 10)，意义如题目所述。
接下来的n行中，每行有一个长度不超过10的彩带字符串Si，只有”2“，”0“，“1”，“4”，四种字符。集合中有可能会有相同的彩带。

输出格式

仅一个整数，表示答案。

样例1

样例输入1

12 1
200

样例输出1

1

样例2

样例输入2

6 2
024
4204

样例输出2

2

限制

每个测试点2s。