Dla ciągów liter x i y, jeżeli można znaleźć dwa ciągi liter u i v takie, że x=uv i y=vu, to x nazywamy cyklicznym przesunięciem y. Innymi słowy, cyklicznym przesunięciem ciągu liter y jest ciąg liter x powstały poprzez przestawienie pewniego zakończenia ciągu y na jego początek. Między innymi cały ciąg jest swoim własnym przesunięciem cyklicznym. Twoim zadaniem jest znalezienie liczby wystąpień cyklicznych przesunięć zadanego wzorca w zadanym tekście.

Zadanie

Napisz program, który:

• wczyta z pliku tekstowego szu.in tekst i wzorzec,
• policzy ile razy cykliczne przesunięcia wzorca występują w tekście,
• zapisze do pliku wynikowego szu.out liczbę wystąpień cyklicznych przesunięć wzorca w tekście.

Wejście

W pierwszym wierszu pliku tekstowego szu.in znajdują się dwie liczby całkowite n (1 <= n <= 1000000) i m (1 <= m <= 1000) oddzielone spacją, oznaczające odpowiednio długość tekstu i długość wzorca. W kolejnym wierszu zapisanych jest n małych angielskich liter nieoddzielonych spacjami. Jest to tekst. W następnym wierszu zapisanych jest m małych angielskich liter nieoddzielonych spacjami. Jest to wzorzec.

Wyjście

Plik tekstowy szu.out powinien zawierać jedną liczbę całkowitą będącą liczbą wystąpień cyklicznych przesunięć wzorca w tekście.

Przykład

Dla pliku wejściowego szu.in:

8 4
aaaabaaa
aaab

poprawną odpowiedzią jest jest plik wyjściowy szu.out:

4