P4987 Palindrome Necklace

**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.

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.

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 one line containing the number of palindromes of length $l$.

**The time limit for each test point is 500 ms.** For $30$% of the data, $n