Bình nghiên cứu DNA. Một xâu DNA chỉ gồm 4 ký tự A, C, G, T. Bình có danh sách các đoạn DNA bị cấm. Hãy đếm số xâu DNA độ dài \(N\) không chứa bất kỳ đoạn cấm nào làm xâu con. Kết quả lấy modulo \(10^9 + 7\).

Định dạng đầu vào

• Dòng đầu: hai số nguyên \(N\) (\(1 \le N \le 100\)) và \(M\) (\(1 \le M \le 100\)).
• \(M\) dòng tiếp theo: mỗi dòng là một xâu cấm, chỉ gồm A, C, G, T, tổng độ dài không quá \(100\).

Định dạng đầu ra

• Một số nguyên là số xâu DNA hợp lệ, modulo \(10^9 + 7\).

Ví dụ

Input:

3 2
A
CC

Output:

27

Ràng buộc