Sətirin bərpası
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, sətirlərlə bəzi əməliyyatlar aparmaq tələb olunur. Məsələn, tez-tez sətir haqqında bəzi məlumatlara əsasən onu bərpa etmək tələb olunur.
Sizə iki sətir S_1 və S_2 verilir. Məlumdur ki, onlardan biri axtarılan sətirin S sonluğu, digəri isə onun başlanğıcı idi. Həmçinin, axtarılan sətirin L uzunluğu və sətirin S yalnız kiçik latın hərflərindən ibarət olduğu məlumdur.
Bu məhdudiyyətlərə cavab verən sətirlərin sayını müəyyən etmək lazımdır. Bu say kifayət qədər böyük ola biləcəyi üçün, onu m modulu ilə çıxış etmək lazımdır.
Giriş verilənləri
Birinci sətir bir tam ədəd t (1 ≤ t ≤ 100) ehtiva edir — emal olunmalı olan məlumat dəstlərinin sayı.
Hər bir məlumat dəstinin təsviri üç sətirdən ibarətdir. Birinci sətir iki tam ədəd ehtiva edir: L və m (1 ≤ L ≤ 10^9, 1 ≤ m ≤ 10^4). İkinci və üçüncü sətirlər müvafiq olaraq S_1 və S_2 sətirlərini ehtiva edir. Onlar boş deyil, kiçik latın hərflərindən ibarətdir və uzunluqları 200 simvoldan çox deyil.
Çıxış verilənləri
Hər bir məlumat dəsti üçün şərtlərə cavab verən sətirlərin sayının m ilə bölünməsindən qalanı ayrıca sətirdə çıxış edin.