Восстановление строки
Во многих прикладных задачах, таких как поиск в сети или расшифровка генома, требуется совершать некоторые действия со строками. Например, часто требуется по некоторым данным о строке восстановить ее саму.
Вам даны две строки S_1 и S_2. Известно, что одна из них была суффиксом искомой строки S, а другая — ее префиксом. Также известна длина искомой строки L, а также то, что строка S состояла только из строчных букв латинского алфавита.
Необходимо определить число строк, удовлетворяющих этим ограничениям. Так как это число может быть достаточно большим, то необходимо вывести его по модулю m.
Входные данные
Первая строка содержит одно целое число t (1 ≤ t ≤ 100) — количество наборов входных данных, которые необходимо обработать.
Описание каждого из наборов входных данных содержит три строки. Первая из них содержит два целых числа: L и m (1 ≤ L ≤ 10^9, 1 ≤ m ≤ 10^4). Вторая и третья строки содержат соответственно строки S_1 и S_2. Они непусты, состоят из строчных букв латинского алфавита, их длины не превышают 200 символов.
Выходные данные
Для каждого набора входных данных выведите в отдельной строке остаток от деления числа строк, удовлетворяющих требованиям условия, на m.