Background

The testdata has been strengthened. Please do not submit brute force solutions anymore.

During the National Day holiday, Big Brother gave Xiaomai a necklace. (Fake. Why would Japanese people celebrate National Day?)

However, Xiaomai was not very happy. She would rather buy a new phone to play games.

Problem Description

But Xiaomai soon discovered something magical about the necklace.

We treat the necklace as an $n$-node cycle, denoted by $s$. Each node on the cycle is a letter from uppercase 'A' to 'Z'. Xiaomai was surprised to find that there are many palindromic strings on the cycle! We define a palindrome as a continuous substring on the cycle whose start and end do not overlap (that is, each node on the cycle can be used at most once), and it satisfies that there exists a palindrome center $i$ such that the characters before $i$ are respectively equal to the characters symmetric to them with respect to the center $i$.

Now, Xiaomai gives you this cycle and wants to know how many essentially different palindromes of length $l$ there are. We consider two palindromes essentially different if and only if the nodes where their palindrome centers are located are different.

Input Format

The first line contains two integers $n$, $l$.

The next line contains $n$ consecutive letters, representing $s_1$, $s_2$, …, $s_n$. Here, $s_i$ is adjacent to $s_i$ $_{mod}$ $_{n+1}$.

Output Format

Output one line containing the number of palindromes of length $l$.

16 1
XIAOMAITAIBANGLE

16

4 3
ABAB

4

Hint

The time limit for each test point is 500 ms.

For $30$% of the data, $n<=20$.

For $50$% of the data, $n<=200$.

For $80$% of the data, $n<=2000$.

For $100$% of the data, $n<=10^6$, $0<l<=n$, and $l$ is odd.

Read the problem carefully. The palindrome in this problem is different from the palindrome in the traditional sense.

Translated by ChatGPT 5