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 ≤ 1015
K ≤ 50
|S| ≤ 3
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor