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 2\,000~

Subtask 2 [90%]

~1 \le |S| \le 1\,000\,000~

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