Chuỗi DNA

Alice đang nghiên cứu về mã di truyền, cô cần tạo ra các chuỗi DNA được biểu diễn bằng xâu nhị phân. Có một số mẫu nhị phân ngắn, được gọi là "mảnh vỡ cấm" có tính chất không ổn định, nếu chúng xuất hiện trong chuỗi DNA như là một xâu con liên tiếp, chúng sẽ gây ra một phản ứng dây chuyền phá hủy chuỗi.

Alice đã xác định được $k$ mảnh vỡ cấm $p_1,p_2,\dots ,p_k$. Để đảm bảo sự ổn định, Alice phải tạo ra các chuỗi DNA nhị phân có độ dài đúng bằng $n$ mà tránh hoàn toàn tất cả $k$ mảnh vỡ cấm, tức là không mảnh vỡ cấm nào xuất hiện trong chuỗi như một xâu con liên tiếp.

Yêu cầu: Cho $n$ và các xâu nhị phân $p_1,p_2,\dots ,p_k$, hãy giúp Alice đếm số lượng chuỗi DNA nhị phân tránh tất cả $k$ mảnh vỡ cấm.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$ $(n\le 200;k\le 10)$.
• Dòng thứ $i$ $(1\le i\le k)$ trong $k$ dòng tiếp theo chứa xâu nhị phân $p_i$ (độ dài các xâu không vượt quá $n$).

Dữ liệu ra

In ra một số nguyên là giá trị $emod111539786$, trong đó $e$ là số chuỗi DNA nhị phân thỏa mãn và $mod$ là phép toán chia lấy dư.

Ràng buộc

• $1\le n\le 200$, $1\le k\le 10$;
• mỗi $p_i$ là xâu khác rỗng chỉ gồm các kí tự $0$ và $1$, $|p_i|\le n$ (các mảnh vỡ có thể trùng nhau).

Subtasks

• Có $40\%$ số test thỏa mãn: $n\le 20$.
• $30\%$ số test khác thỏa mãn: $k=1$.
• $30\%$ số test còn lại không có ràng buộc nào thêm.

Ví dụ