Himi is a very nice girl but also very lazy and inattentive to her studies. So, her tutor decided to teach her a lesson. Each time Himi misses her homework for her laziness, she'll have to do the following task:
Himi will need to build exactly $N$
strings, each containing exactly $M$
characters. The valid alphabets are 'a', 'b', 'c' (all lowercase) or if she wants to leave it empty, she can use '#'. Finally, she has to tell her tutor how many ways she can build such strings.
Here's the catch: each consecutive strings must follow the given rule:
$X$
and (i + 1)-th string is $Y$
and each index is denoted by j. Then, for each alphabet $X[j]$
, $Y[j-1]$
and $Y[j+1]$
must be different from $X[j]$
. If j - 1 or j + 1 is out of bound, you can ignore that condition. She is allowed to leave $Y[j-1]$
and/or $Y[j+1]$
empty (using the '#' character) and the conditions will not apply then.Also, there can not be more than 2 unique alphabets in any string. i.e: "aaba" is a valid string but "aabc" is not.
Himi may be lazy but she's smart. You are the best programmer Himi knows and asked you to write her a program that can do this tiresome work easily.
For your ease, Himi will construct the first string for you following the above mentioned rule. You must not change the first (line number = 1) string.
The first line of the input will be an integer $T$
, the number of test cases.
Each test case will contain two integers $N, M$
and the first string $S$
of length $M$
.
$1 \leq T \leq 50$
$1 \leq M \leq 1$
$1 \leq N \leq 10^7$
$1 \leq T \leq 50$
$1 \leq M \leq 3$
$1 \leq N \leq 5$
$1 \leq T \leq 10$
$1 \leq M \leq 4$
$1 \leq N \leq 10^4$
$1 \leq T \leq 4$
$1 \leq M \leq 4$
$1 \leq N \leq 10^9$
50% test cases on Subtask 3 and 4 will have $M \leq 3$
For each test case, you have to output "Case #X: Y" (without the quotes), where $X$
is the case number and $Y$
is the result modulo $1000000007 \, \, (10^9+7)$
.
Input | Output |
---|---|
2 1 1 a 4 1 # | Case #1: 1 Case #2: 64 |
Input | Output |
---|---|
2 2 2 aa 2 3 aaa | Case #1: 9 Case #2: 27 |