34014번 - NPC 현수막 만들기

문제

성균관대 알고리즘 동아리 NPC는 행사에 필요한 현수막 제작을 요청해, 각 문자의 길이가 1ドル$로 동일하고 총 길이가 $N$인 영어 대문자로 이루어진 문자열 $S$가 인쇄된 원본 현수막을 받았다. NPC 부원들은 필요시 원본 현수막에서 일부 작업을 거쳐 NPC 현수막으로 만들려고 한다.

NPC 현수막을 만들기 위해 원본 현수막에서 아래 작업을 순서대로 할 수 있다.

1. 필요시 원본 현수막의 글자 사이를 잘라 $l, r$이 정수인 연속된 구간 $[l, r]$ $(0 \leq l < r \leq N)$만을 NPC 현수막으로 사용한다. 또한, 원본 현수막의 서로 다른 구간들을 이어 붙여 NPC 현수막으로 만들 수 없다.
2. 필요시 $[l, r]$에 인쇄된 문자 일부를 지운다. 다만, N과 C는 특수 잉크로 인쇄되어 있어 지울 수 없으며 이외 다른 문자들은 모두 지울 수 있다.

두 작업을 완료한 NPC 현수막은 아래 조건들을 모두 만족해야 한다.

• NPC 현수막에는 N, P, C 각각 1ドル$개 문자, 즉 총 3ドル$개의 문자만 왼쪽부터 순서대로 인쇄되어야 한다.
• NPC 현수막의 N과 P 사이의 간격, P와 C 사이의 간격은 서로 동일해야 한다.
• NPC 현수막의 길이는 $L$ 이상, $R$ 이하여야 한다.

이때 NPC 현수막을 만드는 경우의 수를 구해보자. NPC 현수막으로 사용할 원본 현수막의 구간이 다르다면 다른 경우로 본다.

두 구간 $[l_i, r_i]$와 $[l_j, r_j]$이 다름은 $l_i \ne l_j$ 또는 $r_i \ne r_j$일 때 성립한다.

입력

첫째 줄에 받은 원본 현수막의 길이 $N,ドル NPC 현수막의 최소 길이 $L,ドル 최대 길이 $R$이 공백으로 구분되어 주어진다. $(3 \leq N \leq 10^5; 3 \leq L \leq R \leq N)$

둘째 줄에 원본 현수막에 인쇄된 알파벳 대문자로만 이루어진 길이 $N$의 문자열 $S$가 주어진다.

출력

NPC 현수막을 만들 수 있는 경우의 수를 출력한다.

제한

힌트