Restoration of the string#2503
In many practical applications, such as web search or genome decoding, it is necessary to perform some operations on strings. For example, it is often required to restore a string from some information about it.
You are given two strings S_1 and S_2. It is known that one of them was the suffix of the target string , and the other was its prefix. The length of the target string is given, and it is also known that the string consists only of lowercase Latin letters.
You need to determine the number of strings that satisfy these restrictions. As this number can be very large, you need to output it modulo .
The first line contains a single integer (1 \leq t \leq 100) — the number of test cases to process.
Each test case consists of three lines. The first line contains two integers: and (1 \leq L \leq 10^9, 1 \leq m \leq 10^4). The second and third lines contain the strings S_1 and S_2, respectively. They are non-empty, consist of lowercase Latin letters, and their lengths do not exceed characters.
For each test case, output on a separate line the remainder when the number of strings satisfying the conditions is divided by .
Exemple 1