## MLE '19 Contest 2 P1 - FUN

A string is *fun* if it contains each character at most \(K\) times. Given a string \(S\), how many substrings of the string are *fun*? A substring is a **non-empty** contiguous sequence of characters within a string.

#### Input Specification

The first line will contain the string \(S\) \((1 \le |S| \le 10^5)\). The string will only consist of lowercase latin characters.

The second line will contain the integer \(K\) \((1 \le K \le |S|)\).

#### Output Specification

Output the number of substrings that are considered *fun*.

#### Subtasks

##### Subtask 1 [10%]

\(|S| \le 20\)

##### Subtask 2 [20%]

\(S\) will only contain the characters `a`

and `b`

.

##### Subtask 3 [70%]

No further constraints.

#### Sample Input 1 (Subtask 1)

```
abcabca
2
```

#### Sample Output 1

`27`

#### Sample Input 2 (Subtask 2)

```
aaaaaaaaaabbbbbbbbbba
2
```

#### Sample Output 2

`45`

#### Sample Input 3 (Subtask 3)

```
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz
1
```

#### Sample Output 3

`1027`

## Comments