Eggfruit Cake

Time limit0.1sMemory limit512 MB

Summary

Count the circular contiguous slices of a fruit border that contain at least one eggfruit ('E') and at most S fruits, where slices are distinguished by which fruits they include.

Level: Medium7 of 10
Topics: Two pointers, Sliding window, Combinatorics, String
Solved: No attempts yet

Problem

Today is Jaime's birthday, and to celebrate, his friends ordered a cake decorated with eggfruits and persimmons. When the cake arrived, to their surprise, they noticed that the bakery did not use equal amounts of eggfruits and persimmons, but instead scattered the fruits at random around the cake's border.

Jaime eats persimmons every day, so he was eager to try some eggfruit on his birthday. However, he does not want to eat too much, so his cake slice should be decorated with at most S fruits. Since Jaime does not like it when a fruit is cut into parts, each fruit must either be entirely in his slice or be left in the rest of the cake. The problem is that, with the fruits distributed in such a chaotic order, his friends are having trouble cutting a suitable slice for him.

Jaime is about to complain that his friends are taking too long to cut his slice, but to do so, he needs to know how many different slices contain at least one eggfruit and at most S fruits. A slice is defined only by the set of fruits it contains. Since Jaime pays close attention to detail, he can distinguish any two fruits, even if both are of the same type. Hence, two slices are considered different when they do not contain exactly the same set of fruits. The following picture shows one possible cake, as well as the six different slices with at most S = 2 fruits that can be cut from it.

Input

The first line contains a circular string B (3 ≤ |B| ≤ 105) describing the border of the cake. Each character of B is either the uppercase letter "E" or the uppercase letter "P", indicating respectively that there is an eggfruit or a persimmon at the border of the cake. The second line contains an integer S (1 ≤ S < |B|) representing the maximum number of fruits that a slice can contain.

Output

Output a single line with an integer indicating the number of different slices with at most S fruits and at least one eggfruit.

Examples4

Example 1
Input
```
PEPEP
2
```
Expected output
```
6
```
Example 2
Input
```
EPE
1
```
Expected output
```
2
```
Example 3
Input
```
PPPP
1
```
Expected output
```
0
```
Example 4
Input
```
EPEP
2
```
Expected output
```
6
```