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 rows and columns. Each cell within this matrix contains only lowercase letters. Her objective is to navigate from the top-left cell to the bottom-right cell while adhering to the following conditions:
Starting from any cell , she can only move either to the right or downward .
During her journey from cell to cell , 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 times as a substring.
While Nitu acknowledges that there might be multiple paths to reach her destination (from to ), 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, , representing the number of test cases.
For each test case:
The first line includes two integers, and .
The subsequent lines contain strings of length , forming a square matrix.
Following the matrix description, there are additional lines containing her "lucky" string contains only lowercase letters and where means the length of “lucky“ string.
For each test case, please output a single line in the following format: .
Here represents the test case number, and represents the number of paths to reach Nitu's destination (from cell to cell ) modulo .
2 3 2 abc bbc abb bbb 4 3 abcd bbcd abbc xyzp bbb
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.