Sətirin bərpası#2503
Bir çox tətbiqi məsələlərdə, məsələn, şəbəkədə axtarış və ya genomun deşifrə edilməsi kimi hallarda, sətirlərlə bəzi əməliyyatlar aparmaq tələb olunur. Məsələn, bəzən müəyyən məlumatlara əsaslanaraq sətri bərpa etmək lazım olur.
Sizə iki sətir S_1 və S_2 verilir. Məlumdur ki, onlardan biri axtarılan sətirin sonluğu, digəri isə onun başlanğıcı idi. Axtarılan sətirin uzunluğu verilir və həmçinin məlumdur ki, yalnız kiçik latın hərflərindən ibarətdir.
Bu tələblərə cavab verən sətirlərin sayını müəyyənləşdirmək lazımdır. Bu say çox böyük ola biləcəyi üçün onu modulu ilə çıxış etmək lazımdır.
Birinci sətir bir tam ədəd (1 \leq t \leq 100) – emal olunmalı olan testlərin sayı.
Hər test üç sətirdən ibarətdir. Birinci sətir iki tam ədəd: və (1 \leq L \leq 10^9, 1 \leq m \leq 10^4) verir. İkinci və üçüncü sətirlərdə uyğun olaraq S_1 və S_2 sətirləri verilir. Onlar boş deyil, yalnız kiçik latın hərflərindən ibarətdir və uzunluğu -dən çox deyil.
Hər bir test üçün, şərtlərə uyğun sətirlərin sayının -ə bölünməsindən qalan qalığı ayrıca sətirdə çap edin.
Nümunə 1