Yeoksam Station

This problem is fun. It feels like my favorite string quiz. You are given a string $S$ of length $N$ and a positive integer $K$. A string is called a "Yeowoo string" if it has a palindrome of length at least $K$ as a substring. How many distinct substrings of $S$ are Yeowoo strings?

A palindrome reads the same forwards and backwards, such as "기러기", "토마토", "스위스", "인도인", "별똥별", and "우영우". A substring is a contiguous part of a string that is not empty.

For example, when $S$ is "banana" and $K=3$, the distinct substrings of $S$ are the following.

• "a", "an", "ana", "anan", "anana"
• "b", "ba", "ban", "bana", "banan", "banana"
• "n", "na", "nan", "nana"

Of these, the Yeowoo strings are the following 8.

• "ana", "anan", "anana"
• "bana", "banan", "banana"
• "nan", "nana"

The first line contains $N$ and $K$, separated by a space. $\left(1\leq K\leq N\leq 505\,505\right)$

The second line contains the string $S$, which consists only of lowercase English letters.

Print the number of distinct substrings of $S$ that are Yeowoo strings.

If you only focus on counting, you cannot solve this problem. Look at the core idea.