Nguồn đề: HackerEarth https://www.hackerearth.com/problem/algorithm/abcd-strings/description/

Đếm số xâu có độ dài là N, chỉ chứa các kí tự 'a', 'b', 'c', 'd' và không chứa các xâu đặc biệt.

Đáp án có thể rất lớn, hãy chia dư cho 1000000007.

Input

• Dòng đầu tiên chứa T, số testcase. ~( 1 \leq T \leq 200 )~
• Dòng thứ 2 chứa N độ dài của xâu, K số lượng các xâu đặc biệt ~( 1 \leq N \leq 10^{15}, 1 \leq K \leq 50 )~ .
• K dòng tiếp theo mỗi dòng chữa một xâu đặc biệt S. ~( 1 \leq len(S) \leq 3,~ S cũng chỉ chứa các kí tự 'a', 'b', 'c', 'd' )

Output

• Với mỗi testcase, In ra kết quả cần tìm.

Test

• 20đ : ~( 1 \leq N \le 10 )~
• 80đ : ~( 1 \leq N \leq 10^{15} )~

Sample input 1

5
4 8
cac
dbb
abb
ddd
dad
aaa
dbb
cad
3 1
aca
2 7
abb
aac
aab
dcc
bbc
caa
cba
1 4
cbb
ddd
ccb
cdc
5 5
aad
bda
aac
ddb
bdc

Sample output 1

202
63
16
4
789