Lucid Strings

Consider a string over the 26 lowercase English letters. If the length of the string can be written as the product of two positive integers $k$ (≥ 2) and $c$, the string can be split into $k$ substrings of the same length $c$. If those $k$ substrings are pairwise distinct, the string is called a "$k$-Lucid-String" (or "$k$-LS" for short). A substring is a contiguous sequence of characters within a string.

For example, the string ababca has length 6, so it has three cases to check: $k = 2, 3, 6$. For $k = 2$, the string splits into aba and bca, which are distinct, so the string is a 2-LS. For $k = 3$, the string splits into three substrings of length 2, but ab appears twice, so it is not a 3-LS. For $k = 6$, the string splits into six substrings of length 1, but a and b each appear twice, so it is not a 6-LS.

Given a string $S$ of length $n$ and an integer $k$, count the substrings of $S$ that are $k$-LS. Two substrings count separately if they start at different positions in $S$, even when their contents are equal.

For example, take ababca with $k = 2$. Each of the substrings ab, ba, ab, bc, and ca splits into two distinct substrings of length 1, so each is a 2-LS. The substrings babc and abca are also 2-LS, since each splits into two distinct substrings of length 2. The whole string is a 2-LS too, so ababca has 8 substrings that are 2-LS.

The first line contains two integers $n$ (3 ≤ $n$ ≤ 40,000) and $k$ (2 ≤ $k$ ≤ 40,000). Here $n$ is the length of the string and $k$ is the number of equal-length substrings in each $k$-LS. You can assume that $k$ ≤ $n$. The second line contains a string of length $n$.

Print one line containing the number of substrings of the input string that are $k$-LS.