abcd-strings

Please find the number of N-length strings that are made of only letters 'a, 'b', 'c' and 'd' and do not contain any of the restricted strings.

Since, the answer can be very large, please print it modulo 1000000007.

Input Format:

The first line of input file contains T, the number of test cases to follow.
The first line of each test case contains 2 space-separated integers N and K.
The next K lines each contain a string S, which represents a restricted string.

Output Format:

Output T lines, each containing answer to corresponding test case.

Constraints:

T ≤ 200
N ≤ 10^15
K ≤ 50
|S| ≤ 3

SAMPLE INPUT
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
202
63
16
4
789

Source: hackerearth | Difficulty: HARD
Tags: Matrices

Graph algorithms

Complete search


Solutions: