String Reconstruction
Time limit2sMemory limit256 MB
Given length L and two strings, count strings of length L where one string is a prefix and the other a suffix, modulo m.
- Level
Medium7 of 10
- Topics
- String, Combinatorics, Math, Implementation
- Solved
- No attempts yet
Problem
Many applied problems, such as web search or genome decoding, require performing operations on strings. For example, it is often necessary to reconstruct a string from some information about it.
You are given two strings S1 and S2. It is known that one of them is a suffix of the sought string S, and the other is a prefix of it. The length L of the sought string is also known, as is the fact that S consists only of lowercase Latin letters.
You need to determine the number of strings satisfying these constraints. Since this number can be quite large, you must output it modulo m.
Input
The first line contains a single integer t (1 ≤ t ≤ 100), the number of test cases to process.
The description of each test case consists of three lines. The first of them contains two integers L and m (1 ≤ L ≤ 10^9, 1 ≤ m ≤ 10^4). The second and third lines contain the strings S1 and S2, respectively. They are nonempty, consist of lowercase Latin letters, and their lengths do not exceed 200 characters.
Output
For each test case, output on a separate line the remainder of dividing the number of strings satisfying the condition by m.