에그프루트 케이크

오늘은 Jaime의 생일이라 친구들은 에그프루트와 감으로 장식한 케이크를 주문했다. 케이크가 도착했을 때 모두는 빵집에서 에그프루트와 감을 같은 양으로 쓰지 않고, 케이크의 둘레에 과일을 무작위로 흩뿌려 놓은 것을 보고 놀랐다.

Jaime은 감을 매일 먹으므로 생일에는 에그프루트를 먹고 싶어 한다. 그러나 너무 많이 먹고 싶지는 않아서, 그의 케이크 조각에는 기껏해야 S개의 과일이 장식되어 있어야 한다. Jaime은 과일이 여러 조각으로 잘리는 것을 싫어하므로 각 과일은 그의 조각에 통째로 들어가거나 나머지 케이크에 남아 있어야 한다. 문제는 과일이 이렇게 뒤죽박죽으로 흩어져 있어서 친구들이 그에게 알맞은 조각을 자르는 데 애를 먹고 있다는 점이다.

Jaime은 친구들이 조각을 자르는 데 너무 오래 걸린다고 불평하려 하지만, 그러려면 에그프루트를 적어도 하나 포함하고 과일을 기껏해야 S개 포함하는 서로 다른 조각이 몇 개인지 알아야 한다. 조각은 그 조각이 포함하는 과일 집합으로만 정의된다. Jaime은 세부 사항에 꽤 신경을 쓰는 편이라 두 과일이 같은 종류이더라도 구별할 수 있다. 따라서 두 조각이 정확히 같은 과일 집합을 포함하지 않으면 서로 다른 조각으로 본다. 다음 그림은 가능한 케이크 하나와, 그 케이크에서 S = 2 이하의 과일로 자를 수 있는 여섯 개의 서로 다른 조각을 보여 준다.

첫째 줄에는 케이크의 둘레를 나타내는 원형 문자열 B (3 ≤ |B| ≤ 105)가 주어진다. B의 각 문자는 대문자 “E” 또는 대문자 “P”이며, 각각 케이크 둘레에 에그프루트 또는 감이 있음을 나타낸다. 둘째 줄에는 조각이 포함할 수 있는 과일의 최대 개수 S (1 ≤ S < |B|)가 주어진다.

과일을 기껏해야 S개 포함하고 에그프루트를 적어도 하나 포함하는 서로 다른 조각의 개수를 한 줄에 정수로 출력한다.