Відновлення рядка#2503
У багатьох прикладних задачах, таких як пошук у мережі або розшифровка геному, потрібно виконувати певні операції з рядками. Наприклад, часто виникає потреба відновити рядок на основі наданої інформації про нього.
Вам дано два рядки S_1 і S_2. Відомо, що один з них був суфіксом шуканого рядка , а інший — його префіксом. Відома довжина шуканого рядка , і також відомо, що рядок складається лише з малих латинських літер.
Потрібно визначити кількість рядків, які задовольняють цим обмеженням. Оскільки це число може бути дуже великим, потрібно вивести його за модулем .
Перший рядок містить одне ціле число (1 \leq t \leq 100) — кількість тестових випадків.
Кожен тестовий випадок складається з трьох рядків. Перший рядок містить два цілих числа: і (1 \leq L \leq 10^9, 1 \leq m \leq 10^4). Другий і третій рядки містять рядки S_1 і S_2 відповідно. Вони непорожні, складаються з малих латинських літер, а їх довжина не перевищує символів.
Для кожного тестового випадку виведіть у окремому рядку залишок від ділення кількості рядків, що задовольняють умові, на .
Приклад 1