Limits 4s, 512 MB

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:

  • Let's assume i-th string is $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.

Input

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$.

Constraints

Subtask 1: (5 Points)

$1 \leq T \leq 50$
$1 \leq M \leq 1$
$1 \leq N \leq 10^7$

Subtask 2: (15 Points)

$1 \leq T \leq 50$
$1 \leq M \leq 3$
$1 \leq N \leq 5$

Subtask 3: (upto 30 Points)

$1 \leq T \leq 10$
$1 \leq M \leq 4$
$1 \leq N \leq 10^4$

Subtask 4: (upto 50 Points)

$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$

Output

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)$.

Samples

InputOutput
2
1 1 a
4 1 #
Case #1: 1
Case #2: 64
InputOutput
2
2 2 aa
2 3 aaa
Case #1: 9
Case #2: 27

Submit

Login to submit.

Statistics

80% Solution Ratio
YouKnowWhoEarliest, Jul '20
Salman.306242Fastest, 1.4s
YouKnowWhoLightest, 864 kB
Salman.306242Shortest, 3090B
Toph uses cookies. By continuing you agree to our Cookie Policy.