Problem Background

The data has been enhanced, so please do not submit brute force solutions anymore.

During the National Day holiday, brother gave Umari a necklace. (Fake, what National Day do Japanese people celebrate?)

However, Umari was not very happy; she would rather buy a new phone to play games.

Problem Description

But Umari quickly discovered the magical aspect of the necklace.

We consider the necklace as an $n$-element ring, denoted as $s$, where each node on the ring is composed of a letter from 'A' to 'Z'. Umari was amazed to find that there are many palindromic strings on the ring! We define a palindromic string as a continuous substring on the ring that does not overlap at the ends (i.e., each node on the ring is used at most once) and satisfies the existence of a palindrome center $i$, such that several characters before $i$ are identical to their symmetric characters with respect to $i$.

Now, Umari gives you this ring and wants to know how many distinct palindromic strings of length $l$ exist; we consider two palindromic strings distinct if and only if their palindrome centers are at different nodes.

Input Format

The first line contains two numbers $n$ and $l$.

The next line reads $n$ consecutive letters representing $s_1, s_2, \ldots, s_n$; where $s_i$ is adjacent to $s_{i \mod (n+1)}$.

Output Format

A single line indicating the number of palindromic strings of length $l$.

Sample Input and Output

Sample Input #1

16 1
XIAOMAITAIBANGLE

Sample Output #1

16

Sample Input #2

4 3
ABAB

Sample Output #2

4

Notes

The time limit for each test case is 500ms.

For 30% of the data, $n \leq 20$.

For 50% of the data, $n \leq 200$.

For 80% of the data, $n \leq 2000$.

For 100% of the data, $n \leq 10^6$, $0 < l \leq n$ and $l$ is an odd number.

Read the problem carefully, as the palindromic strings in this problem are different from the traditional definition.

见题面 Input 部分

见题面 Output 部分