Mimi is playing with a string $S$ when her little sister asks her a question:

How many substrings of $S$ are there such that these substrings are of length $K$ and have exactly 1 distinct letter?

Constraints

Let $|S|$ denote the length of $S$.

For all subtasks:

$1\le K\le |S|$

Subtask 1 [10%]

$1\le |S|\le 2000$

Subtask 2 [90%]

$1\le |S|\le 1000000$

Input Specification

The first line of input will contain a single string, $S$, consisting of only lowercase English letters.
The second line of input will contain an integer, $K$.

Output Specification

The number of substrings which satisfy the given condition.

Sample Input

aaaabb
2

Sample Output

4