题目描述

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

• 该串是回文串；
• 在给定的 $k$ 个串中，该串不存在两个不重叠的子串。

即不存在 $a \le b < c \le d$，$S_{a \sim b}$ 是 $k$ 个串中的一个，$S_{c \sim d}$ 是 $k$ 个串中的一个。

举个例子，若给定 $2$ 个 $01$ 串 （即 $k=2$）：101 和 1001 。那么 1010001 和 1010101 均不满足条件。前者不满足条件一，后者不满足条件二。

输入格式

第一行两个整数 $n,k$。
以下 $k$ 行，每行一个 $01$ 串。

输出格式

输出一个整数表示答案，答案对 $10^9+7$ 取模。

5 1
0

2

数据规模与约定

对于 $100\%$ 的数据，$n \le 100$，$k \le 20$，$L \le 10$。