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¹⁵
K ≤ 50
|S| ≤ 3