All Tracks Math Problem
SOLVE
LATER
ABCD Strings
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
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
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...
Contributor
This Problem was Asked in
OTHER PROBLEMS OF THIS CHALLENGE
-
Basic Programming > Implementation
-
Algorithms > Searching
-
Math > Number Theory
