Xâu ABCD
Hãy đếm số xâu có độ dài $N$, chỉ gồm các kí tự a,b,c,d mà không chứa các xâu $S_1,S_2,...,S_k$.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $T \ (0<T\le 50)$ - số lượng testcase;
- Mỗi testcase mô tả như sau: - Dòng đầu tiên số nguyên $N, k \ (0<N\le 10^{18}; 0<k\le 50)$;
- $k$ dòng tiếp theo, mỗi dòng chứa một xâu $S_i \ (|S_i|\le3)$.
Kết quả
- In $T$ dòng, mỗi dòng là kết quả của mỗi testcase sau khi chia lấy dư cho $10^9+7$.
Ví dụ
Ví dụ 1
input
1
4 8
cac
dbb
abb
ddd
dad
aaa
dbb
cad
output
202
Ví dụ 2
input
2
3 1
aca
2 7
abb
aac
aab
dcc
bbc
caa
cba
output
63
16
Comments