Tránh mẫu 2

Xâu nhị phân \(S\) được gọi là tránh mẫu nhị phân \(P\) , nếu \(P\) không xuất hiện trong \(S\).
Cho \(n\) và \(k\) xâu nhị phân \(P_{1}, P_{2}, ..., P_{k}\), hãy đếm số xâu nhị phân độ dài \(n\) tránh tất cả các mẫu \(P\).

Input

Dòng đầu chứa số nguyên \(n\) và \(k\)

\(k\) dòng tiếp theo, dòng thứ \(i\) trong chứa xâu nhị phân \(P_{i}\) độ dài không quá \(n\).

Output

Gồm nhiều dòng, mỗi dòng là đáp án tương ứng với bộ dữ liệu vào, vì kết quả có thể rất
lớn nên kết quả đưa ra là phần dư cho \(111539786\).

Example

2 2
00
01

2

Scoring

Subtask \(1\) tương ứng với \(30\%\) số điểm: \(n \leq 20\)

Subtask \(2\) tương ứng với \(30\%\) số điểm: \(n \leq 200\), \(k = 1\).

Subtask \(3\) tương ứng với \(40\%\) số điểm: \(n \leq 200\).