당신은 남북 방향으로 길게 뻗은 많은 도로와 동서 방향으로 길게 뻗은 많은 도로가 있는 도시에 살고 있다. 인접한 두 남북 방향 도로 사이의 거리는 $1\text{ km}$이다. 마찬가지로, 인접한 두 동서 방향 도로 사이의 거리도 $1\text{ km}$이다.
이 도시에는 시청이 하나 있다. 시청이 위치한 교차점을 $(0,0)$이라 하자. 이 도시의 교차점은 두 정수 $i, j$를 사용하여 $(i, j)$로 나타낸다. 즉, 교차점 $(i, j)$는 교차점 $(0,0)$에서 동쪽으로 $i\text{ km}$($i < 0$이면 서쪽으로 $-i\text{ km}$), 북쪽으로 $j\text{ km}$($j < 0$이면 남쪽으로 $-j\text{ km}$) 이동한 위치이다.
시청에서는 Joy라는 이름의 개를 기르고 있다. Joy는 $K$일 동안의 산책 계획을 세웠다. 산책 계획은 다음과 같다:
- $K$일 중 첫째 날 아침에 Joy는 교차점 $(0,0)$에 있다. Joy는 교차점 $(0,0)$에 표시를 남긴다. Joy는 $(0,0)$ 이외의 어떤 교차점에도 표시를 남기지 않은 상태이다.
- Joy는 $K$일 동안 매일 낮에 산책을 한다. 하루 동안의 산책은 $N$번의 이동으로 이루어진다. 각 이동에서 Joy는 현재 교차점에서 인접한 교차점으로 이동하고 도착한 곳에 표시를 남긴다. 낮 동안 Joy가 이동하는 방식은 매일 동일하다.
- 낮 동안의 이동이 끝나면 Joy는 다음 날 아침까지 현재 교차점에서 잠을 잔다.
시청에서는 $K$일간의 산책으로 만들어진 Joy의 영역(territory)에 대해 논의하고 있다. 네 교차점 $(a,b), (a+1,b), (a+1,b+1), (a,b+1)$로 둘러싸인 구역은 Joy가 이 네 교차점 모두에 적어도 한 번씩 표시를 남겼을 때 Joy의 영역에 속한다.
당신은 Joy의 산책 계획을 바탕으로 Joy의 영역에 속하는 구역의 개수를 계산하는 프로그램을 작성해야 한다.
이 도시의 도로들은 매우 길고 남북 방향과 동서 방향 모두 도로가 충분히 많기 때문에, 산책 도중 Joy가 도로의 끝에 도달하거나 도시의 가장자리에 도달하는 일은 없다.
입력
표준 입력에서 다음 입력을 읽어들인다:
- 첫째 줄에는 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다. 이는 하루의 산책이 $N$번의 이동으로 이루어지며 산책 계획이 $K$일에 걸쳐 있음을 나타낸다.
- 둘째 줄에는 길이 $N$인 문자열 $S$가 주어진다. 문자열 $S$의 왼쪽에서 $p$번째 문자 $C_p$($1 \le p \le N$)는 'E', 'N', 'W', 'S' 중 하나이다. 이 문자들은 다음을 나타낸다:
- 문자 $C_p$가 'E'이면, $p$번째 이동에서 동쪽에 있는 교차점으로 이동함을 의미한다.
- 문자 $C_p$가 'N'이면, $p$번째 이동에서 북쪽에 있는 교차점으로 이동함을 의미한다.
- 문자 $C_p$가 'W'이면, $p$번째 이동에서 서쪽에 있는 교차점으로 이동함을 의미한다.
- 문자 $C_p$가 'S'이면, $p$번째 이동에서 남쪽에 있는 교차점으로 이동함을 의미한다.
여기서 교차점 $(i, j)$에 대해 동쪽, 북쪽, 서쪽, 남쪽에 있는 교차점은 각각 $(i+1, j)$, $(i, j+1)$, $(i-1, j)$, $(i, j-1)$이다.
출력
Joy의 영역에 속하는 구역의 개수를 표준 출력에 한 줄로 출력하라.
제한
모든 입력 데이터는 다음 조건을 만족한다:
- $1 \le N \le 100\,000$.
- $1 \le K \le 1\,000\,000\,000$.
서브태스크
서브태스크 1 [5점]
- $N \le 50$.
- $K = 1$.
서브태스크 2 [10점]
- $K = 1$.
서브태스크 3 [23점]
- $N \le 50$.
서브태스크 4 [62점]
- 추가 제한 조건이 없다.
예제
입력 1
12 1 EENWSEEESWWS
출력 1
3
참고
이 예제에서는 1일 동안 산책을 수행한다. 첫째 날에 Joy는 시청에서 출발하여 아래 그림과 같이 이동한다. 검은색 원은 Joy가 표시를 남긴 교차점이고, 흰색 원은 Joy가 표시를 남기지 않은 교차점이며, 이중 원은 시청이 위치한 교차점이고, 숫자는 각 이동 단계를 나타낸다.
Joy의 이동 경로
예제 1에서는 아래 그림에서 음영으로 표시된 3개의 구역이 Joy의 영역에 속한다.
예제 1에서 Joy의 영역
입력 2
12 2 EENWSEEESWWS
출력 2
7
참고
예제 2에서는 2일에 걸쳐 산책을 수행한다. 매일의 이동 경로는 예제 1과 동일하다. 산책이 완료되면 아래 그림에서 음영으로 표시된 7개의 구역이 Joy의 영역에 속한다.
예제 2에서 Joy의 영역
입력 3
7 1 ENNWNNE
출력 3
0
참고
예제 3에서는 Joy의 영역에 속하는 구역이 없다.
입력 4
16 5 WSESSSWWWEEENNNW
출력 4
21