P13984 [HackerEarth] 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.
提高
题目描述

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

输入格式

见题面

输出格式

见题面

样例输入
100 98538 2 dbc bda 18766 3 ac bd ccd 6515 7 cab bb dba dab dac abd dcd 98095 1 bdc 57671 10 dcb dcd baa bb ccb bcc dbb bcc abd add 22126 7 aac cac cc aca adc caa aaa 42011 5 cdd bcd ad dcc aad 83141 4 dcb aaa aad cbb 51051 9 bba dbb dcd dba abd cbc add abb dbd 37191 6 adb dcd bb cca cbc cc 39530 5 bcc adc bda aac abd 98318 5 ada ccb abc aba aad 8791 0 63365 4 cca dbb acc dab 77374 7 add bcb ccb bca ddc bbb dba 21265 9 aba bcb dc dab cbd bba d acd acb 24934 0 66350 5 bcc bd abb cda aaa 84568 2 ddd bdd 34025 9 bbc ac cda cd ddc bab cbc cad dad 87797 2 dbd cb 3099 10 acc dc abc dca acb dbc dba cca bcb ac 99283 5 aba baa bcd cca bcc 71917 10 dad dda aca bcc bcd adc dcd dac cac bad 58940 8 aac ddc bb bcb dcb bcd aaa bba 87968 5 acc dbc aba cad aad 3106 1 cba 8465 9 dbd bab acb aaa cdd add dca cbb bad 1829 10 bbd cab cd baa adc cdd dab aac bab aaa 55304 10 bad bca cbb cac db ddb bc abd adb aab 28933 1 bb 31693 4 cdb bbd cda bd 75135 2 ab ddb 22671 8 cbd bdb dbc ddd bcb bbd dcb ddd 16412 8 abb aac bac bbb abd dda ccb cdc 85557 6 adb dcd bcb cad abb aba 65358 4 bac bca abd cbc 8470 7 aad bac cdb dad acb cda bdd 44941 9 dab bbd dda cbc ca dcd cb bda cda 46822 1 acd 81113 9 cbb dcc dca bab cdc dac ddd ccd bba 57984 5 bbc dac bad bbb cba 42308 5 aaa add aad adc baa 77330 3 bab dab add 17892 9 aad ddb cd aa bbc dda acc cda aaa 23620 6 ada ddd adc dbb cac dcc 38602 0 58309 10 bcb cdc ca aba dad da abc bbc add bca 87773 6 dcc bbd bad abb bba cad 65945 8 cdd acb aba dda ccb dac acc cda 67592 7 dca cbd dad acb bdc aac cac 20690 4 cca cdc bca cbb 5397 0 27146 4 bad bbc bac baa 11307 9 bca cad bab cca ac cab ccc dca ddd 49661 1 dbb 18574 4 baa dbd bdc cac 94849 5 dbc db bdd ccb bdc 88117 2 ccc bcc 51551 0 30667 3 dad ccc bdc 719 4 dcd cba acd bcd 53826 3 cdc aba dd 75479 9 aac cac ddb abb bac bac caa abc bd 87792 9 bcb bbb adc aac adb cbd aaa bda ad 60907 6 dcc cda bbc dbd bb dab 73644 9 dba cdd bbb dda ccc baa dac aba cac 39070 7 dd acb bcd cbd dac caa aab 11357 9 bca cbb cd abd aad cb ddd bba cab 16372 1 dbb 55992 1 dac 774 2 caa dbd 82092 9 dcc bcc bdd cad bbb aac ccd cbb dad 6965 1 ddc 7638 5 ddd adc ada bc daa 82960 9 dda cda cca abb cad caa aaa dbd ad 504 9 ccc aca cdd bbd ada ddd dd ba ada 27851 5 dab ccd bad dcc cca 84490 4 bca baa bcb cdc 72576 6 caa bcc bca aca adb dac 62084 7 bbc abc dcd aab bda aca bbc 47990 10 bdd abc aca bbb dac ba adb dda acc bba 59982 0 78348 0 89018 9 bab cab cdc da dbc aca dcb acd bcb 41725 6 aaa aba bda bcb aad ddb 72091 6 dcc acd bda ddc aba baa 48785 6 bbb db bcb bad dcb bcc 81064 6 cab bdd add ada ddd aba 25199 0 58785 0 11630 9 ada adc bac dcb aba bdd baa dcc aba 31903 3 aca acb bdd 58815 7 baa ada abd aad dba aaa dac 32636 5 bdb bad baa cdc cba 3769 5 bbd abb abc bda dcd 33499 10 bab bcc adb cbc dda bdd abd dcd ccb bca 29177 0 53533 10 ccc cdb dcb cbb cab ad bda cbd bcc bca 13956 5 cad ccc acb bbc daa
样例输出
233 120132 369902 4359 1366426