spoj 4660 Binary palindrome二进制回文串

时间限制:10s      空间限制:256MB

题目描述

给定k个长度不超过L的01串,求有多少长度为n的01串S满足:

1.该串是回文串

2.该串不存在两个不重叠的子串,在给定的k个串中。

即不存在a<=b<c<=d,S[a,b]是k个串中的一个,S[c,d]是k个串中的一个

(It does not contain two non-overlapped substrings in the given list of K binary strings.)

举个例子,若给定2(k=2)个01串:101和1001

1010001和1010101均不满足条件。前者不满足条件1,后者不满足条件2


输入格式

第一行两个整数n,k

以下k行,每行一个01串


输出格式

输出一个整数表示答案,答案mod 1000000007(10^9+7)


样例输入

5 1
0

样例输出

2

提示

n<=100,k<=20,L<=10


题目来源

没有写明来源