체스에서 rook은 가로, 세로 방향으로 어느 곳이나 한 번에 움직일 수 있다.

즉 다음과 같은 체스판에서 rook이 X 라고 표시된 위치에 있을 때,

그 다음 rook이 움직여 갈 수 있는 부분은 어둡게 칠해진 부분 중의 하나이다.

N × 1,000,000 크기의 체스판이 주어졌다.

체스판의 i번째 행에는 1열부터 W[i]열까지의 칸을 제외한 모든 칸에 장애물이 놓여있다.

우리는 거기에 K개의 rook을 배치하려고 하는데, 모든 rook들은 서로 잡아먹을 수 없어야 한다.

그렇다면 rook들을 어떻게 배치해야만 할까?

단, 장애물이 있는 곳에는 rook을 놓을 수가 없다.

장애물을 사이에 두고 rook을 배치하면 잡아먹을 수 없다.

가능한 모든 경우의 개수를 출력한다.

N Rook 3 timer 1s memory 512MB

N Rook 3 1s 512MB