Description

Original source: 2014 Hubei Provincial Team Selection Test Week2

"Madoka, don't trust QB!" With Homura's desperate cry, Madoka formed a contract with QB.

This was one of Madoka's nightmares and also an event from the previous timeline. To prevent Madoka from forming a contract with QB this time, Homura decided to eliminate QB on the very first day of school. However, QB has many avatars (though episode 8 suggests it might be infinitely respawning). Nevertheless, the determined Homura will not give up—she resolves to destroy everything that could possibly be QB. Now, she has sensed the nearby conditions and converted them into a string of length $n$, which she has given to you, an OI student.

From her words, you now know that all substrings of the form $A+B+A$ are QB or its avatars, where $|A|\ge k$ and $|B|\ge 1$ (substrings at different positions but otherwise identical are considered distinct, while substrings at the same position but split differently are considered the same). You must quickly tell Homura the answer—the count of QB and its avatars.

Note: For a string $S$, $|S|$ denotes the length of $S$.

Input Format

The first line contains a string $S$, and the second line contains an integer $k$.

Output Format

Only one line with an integer $\text{ans}$, representing the count of QB and its avatars.

Sample 1

aaaaa
1

6

Sample 2

abcabcabc
2

8

Data Range and Hints

For all data, $1\le |S|\le 1.5\times 10^4$, $1\le k\le 100$, and the character set consists of all lowercase letters.