Відновлення рядка
У багатьох прикладних задачах, таких як пошук у мережі або розшифровка геному, потрібно виконувати певні операції з рядками. Наприклад, часто виникає потреба відновити рядок на основі наданої інформації про нього.
Вам дано два рядки 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.