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.

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.

Input

• 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~).

Output

• Ghi ra một số nguyên là giá trị ~e \pmod{111539786}~, trong đó ~e~ là số chuỗi DNA nhị phân thỏa mãn và phép toán ~%~ là phép toán chia lấy dư.

Subtasks

• 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.

Sample Input 1

2 1
0

Sample Output 1

2

Sample Input 2

2 2
00
10

Sample Output 2

2