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?
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~
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~.
The number of substrings which satisfy the given condition.