Xâu ABCD


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.