Circular Necklace Palindrome Centers

Consider a necklace represented as a circular array of n characters, each being an uppercase letter from 'A' to 'Z'. We treat the necklace as a ring, and any contiguous subsequence (without reusing any node) is a candidate substring. A substring is defined to be a palindrome if and only if there exists a palindrome center at some node i such that the characters preceding i (in the selected substring) mirror correspond exactly to the characters following i (with the symmetry defined with respect to i). In other words, if the substring is of odd length l, and if we denote half = \(\frac{l-1}{2}\), then the substring starting at some index and ending after l nodes is palindromic if for every j from 0 to \(half\), the character at position (start+j) mod n is equal to that at position (start+l-1-j) mod n (with indices taken modulo n due to the circular structure).

Two palindromic substrings are considered essentially different if and only if the node corresponding to their palindrome center differs. Given the necklace and an integer l (which represents the intended odd length of the substring), your task is to compute the number of essentially different palindromic substrings of length l.

Note: If l is even or if l > n, no valid palindromic substring as defined exists, so the answer is 0.

The palindrome condition in LaTeX format is expressed as: A substring of length \(l\) (with \(l\) odd) and starting at index \(s\) is palindromic if \[ \forall \; 0 \le j \le \frac{l-1}{2}, \quad s[(s+j)\,\%\,n] = s[(s+l-1-j)\,\%\,n]. \]

inputFormat

The first line contains two integers n and l (1 \le l \le n), where n is the length of the necklace and l is the length of the substring to check.

The second line contains a string of length n consisting only of uppercase letters 'A' to 'Z'.

outputFormat

Output a single integer, the number of essentially different palindromic substrings of length l. Two substrings are considered essentially different if their palindrome centers (i.e. the index corresponding to the center of the palindrome) are different.

sample

5 3
ABCBA

1