크레이지 서치

많은 사람들이 어려운 퍼즐 풀기를 좋아하며, 그중 일부는 사람을 미치게 만들 만큼 까다롭습니다. 그런 퍼즐 중 하나는 주어진 글에 숨어 있는 어떤 수를 찾는 것입니다. 예컨대 그 수는, 글 안에 등장하는 정해진 길이의 서로 다른 부분 문자열의 개수일 수 있습니다. 곧 알게 되겠지만, 이 문제를 손으로 푸는 것은 사실상 불가능하며 컴퓨터와 좋은 알고리즘이 필요합니다.

부분 문자열의 길이 $N$, 글에 나타날 수 있는 서로 다른 문자의 개수 $NC$, 그리고 글 자체가 주어질 때, 그 글에 등장하는 길이 $N$짜리 서로 다른 부분 문자열이 몇 개인지 세는 프로그램을 작성하세요. 부분 문자열이란 연속한 문자들의 묶음이며, 두 부분 문자열은 문자 단위로 완전히 같을 때에만 같은 것으로 봅니다. 각 서로 다른 부분 문자열은 글 안에서 몇 번 나타나든 한 번만 셉니다.

$N = 3$, $NC = 4$, 글이 daababac인 경우를 생각해 봅시다. 이 글에 등장하는 길이 3짜리 부분 문자열은 daa, aab, aba, bab, bac입니다. (aba는 두 번 나타나지만 한 번만 셉니다.) 따라서 답은 $5$입니다.

첫째 줄에 두 정수 $N$과 $NC$가 공백 하나로 구분되어 주어집니다. 그 뒤에 탐색 대상이 되는 글이 주어집니다. 가능한 문자 집합으로 만들 수 있는 부분 문자열의 총 개수는 1600만을 넘지 않는다고 가정해도 됩니다. 즉, $NC^N \le 16{,}000{,}000$입니다.

글에 등장하는 길이 $N$짜리 서로 다른 부분 문자열의 개수를 정수 하나로 출력합니다.