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 một mảnh vỡ cấm xuất hiện trong chuỗi DNA như một xâu con liên tiếp, nó sẽ gây ra 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, \ldots, p_k~. Để đảm bảo sự ổn định, Alice cần tạo ra các chuỗi DNA nhị phân có độ dài đúng bằng ~n~ và không chứa bất kỳ mảnh vỡ cấm nào dưới dạng xâu con liên tiếp.

Hãy đếm số lượng chuỗi DNA nhị phân thỏa mãn yêu cầu trên.

Input

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

Output

In ra một số nguyên là số lượng chuỗi DNA nhị phân độ dài đúng bằng ~n~ không chứa bất kỳ xâu ~p_i~ nào dưới dạng xâu con liên tiếp, lấy dư cho ~111539786~.

Ràng buộ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ụ 1

Input

2 1
0

Output

1

Ví dụ 2

Input

2 2
00
10

Output

2

Giải thích

• Ở ví dụ 1, chỉ có xâu 11 không chứa ký tự 0, nên đáp án là ~1~.
• Ở ví dụ 2, hai xâu hợp lệ là 01 và 11.