All Tracks Math Problem

ABCD Strings
Tag(s):

Algorithms, Graph Theory, Hard, Linear Algebra, Mathematics, Matrix Exponentiation, Recursion

Problem
Editorial
Analytics

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

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
Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

Remember December

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?