루시드 스트링

영어 소문자 26개로 이루어진 문자열을 생각하자. 문자열의 길이가 두 양의 정수 $k$ (≥ 2)와 $c$의 곱으로 표현되면, 그 문자열을 길이가 $c$로 같은 부분 문자열 $k$개로 나눌 수 있다. 나눈 $k$개의 부분 문자열이 모두 서로 다르면, 그 문자열을 "$k$-Lucid-String" (줄여서 "$k$-LS")이라고 한다. 부분 문자열은 문자열 안에서 연속된 문자들의 묶음이다.

예를 들어 길이가 6인 ababca는 $k = 2, 3, 6$의 세 경우를 확인해야 한다. $k = 2$일 때 aba와 bca로 나뉘고 서로 다르므로 2-LS이다. $k = 3$일 때는 길이 2인 부분 문자열 3개로 나뉘지만 ab가 두 번 나오므로 3-LS가 아니다. $k = 6$일 때는 길이 1인 부분 문자열 6개로 나뉘지만 a와 b가 각각 두 번 나오므로 6-LS가 아니다.

길이가 $n$인 문자열 $S$와 정수 $k$가 주어졌을 때, $S$의 부분 문자열 중 $k$-LS인 것의 개수를 구하라. 내용이 같더라도 $S$에서 시작 위치가 다르면 각각 따로 센다.

예를 들어 $k = 2$일 때 ababca의 부분 문자열 ab, ba, ab, bc, ca는 모두 서로 다른 길이 1의 부분 문자열 2개로 나뉘므로 2-LS이다. 부분 문자열 babc와 abca도 길이 2인 서로 다른 부분 문자열 2개로 나뉘므로 2-LS이다. 문자열 전체도 2-LS이므로, ababca에는 2-LS인 부분 문자열이 8개 있다.

첫 줄에 두 정수 $n$ (3 ≤ $n$ ≤ 40,000)과 $k$ (2 ≤ $k$ ≤ 40,000)가 주어진다. $n$은 문자열의 길이이고, $k$는 각 $k$-LS를 이루는 같은 길이 부분 문자열의 개수이다. $k$ ≤ $n$이라고 가정해도 된다. 둘째 줄에는 길이가 $n$인 문자열이 주어진다.

입력된 문자열의 부분 문자열 중 $k$-LS인 것의 개수를 한 줄에 출력한다.