패턴

블라덱이 가장 좋아하는 주제는 패턴 검색 문제입니다. 텍스트 알고리즘 강의를 들으며 그는 이 문제를 푸는 여러 방법을 고안했지만, 기말고사에서는 다음과 같은 변형을 풀어야 했습니다: 패턴 $P$와 텍스트 $T$가 주어질 때, 임의로 확대한 $P$는 $T$ 안에서 몇 번 나타나는가?

패턴을 $k$배 확대한다는 것은 패턴의 각 글자를 같은 글자 $k$개로 바꾸는 것입니다. 예를 들어 패턴 aabc를 차례로 확대하면 aabc(1배), aaaabbcc(2배), aaaaaabbbccc(3배), aaaaaaaabbbbcccc(4배), ... 가 됩니다.

임의로 확대한 $P$가 나타나는 위치란, 어떤 정수 $k \ge 1$에 대해 $k$배 확대한 $P$가 $T$의 $i$번째 글자부터 시작하여 나타나는 위치 $i$를 말합니다. 한 위치 $i$에서 서로 다른 확대 배수 여러 개가 동시에 시작하더라도 그 위치는 한 번만 셉니다(두 번째 예제 참고).

$T$ 안에서 임의로 확대한 $P$가 나타나기 시작하는 서로 다른 위치의 개수를 구하세요.

첫째 줄에 공백 하나로 구분된 두 정수 $n$과 $m$이 주어집니다 ($1 \le n, m \le 10^6$). 둘째 줄에는 소문자 알파벳 $n$개로 이루어진 텍스트 $T$가 주어집니다. 셋째 줄에는 소문자 알파벳 $m$개로 이루어진 패턴 $P$가 주어집니다.

어떤 배수로든 확대한 패턴이 텍스트 안에서 나타나기 시작하는 위치의 개수를 한 줄에 출력하세요.