Limits 2s, 512 MB

Recently, Nitu has developed a keen interest in solving string-related problems. She possesses a special 'lucky' string. Just last week, Nitu stumbled upon a fascinating puzzle involving a square matrix, consisting of NN rows and NN columns. Each cell within this matrix contains only lowercase letters. Her objective is to navigate from the top-left cell (0,0)(0, 0) to the bottom-right cell (N1,N1)(N - 1, N - 1) while adhering to the following conditions:

  • Starting from any cell (i,j)(i, j), she can only move either to the right (i,j+1)(i, j + 1) or downward (i+1,j)(i + 1, j).

  • During her journey from cell (0,0)(0, 0) to cell (N1,N1)(N - 1, N - 1), she must collect all the letters encountered along the way. Subsequently, she will construct a string using these letters, and this string must contain her 'lucky' sequence at least MM times as a substring.

While Nitu acknowledges that there might be multiple paths to reach her destination (from (0,0)(0, 0) to (N1,N1)(N - 1, N - 1)), she claims to have solved the problem in a single attempt and is now challenging you. Are you prepared to accept her challenge?


The first line comprises an integer, TT (1T100)(1 \leq T \leq 100), representing the number of test cases.

For each test case:

The first line includes two integers, NN (1N100)(1 \leq N \leq 100) and MM (0M10)(0 \leq M \leq 10).

The subsequent NN lines contain strings of length NN, forming a square matrix.

Following the matrix description, there are additional lines containing her "lucky" string contains only lowercase letters and 1lucky100 1\leq |\text{lucky}|\leq 100 where lucky|\text{lucky}| means the length of “lucky“ string.


For each test case, please output a single line in the following format: Case #X: Y\texttt{Case \#}X\texttt{: }Y.

Here XX represents the test case number, and YY represents the number of paths to reach Nitu's destination (from cell (0,0)(0, 0) to cell (N1,N1)(N - 1, N - 1)) modulo 109+710^{9} + 7.


3 2
4 3
Case #1: 2
Case #2: 0

In the first input, Nitu can go (0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2)

From this path she can make a string abbbb. This string contains her lucky string bbb 2 times as a substring.

A substring is a contiguous sequence of characters within a larger string.


Login to submit.


89% Solution Ratio
ApuOrghoEarliest, 7M ago
YouKnowWhoFastest, 0.4s
sakib_safwanLightest, 42 MB
abid1729Shortest, 1304B
Toph uses cookies. By continuing you agree to our Cookie Policy.