hint

이 문제는 N×N 격자에 있는 로봇이 1번 칸에서 NM 번 칸으로 가는 서로 다른 경로의 개수를 세는 문제이다. 이때, 로봇은 인접한 오른쪽 또는 아랫방향으로만 이동 할 수 있으며 O표가 쳐진 칸이 존재 할 때는 그 칸을 무조건 지나야 한다.

K=0 인 경우에는 아래와 같이 여러 가지 방법으로 답을 구할 수 있으며 K ≠0 인 경우(O 표가 있는 경우)에는 K = 0 인 경우의 해법을 두 번 사용해 해결할 수 있다.

K=0 인 경우의 답을 구하는 가장 간단한 방법으로 1번 칸에서 NM 번 칸으로 가는 모든 경로를 DFS(Depth First Search)를 이용해 직접 탐색하여 수를 셀 수 있으며, 이 방법으로도 만점을 받을 수 있다.

두 번째 방법은 다이나믹 프로그래밍을 이용한 계산 방법이다. 특정 격자 (Y,X)에 로봇이 도달하려면 로봇은 반드시 (Y-1,X) 혹은 (Y,X-1)격자에서 한 칸 이동해야 한다. 즉, 격자 (Y,X)에 로봇이 갈 수 있는 경우의 수를 Dy,x 라 하면 Dy,x = Dy-1,x + Dy,x-1 가 된다. 위의 식을 D1,1부터 순서대로 채우면 1번 칸에서 특정 칸으로 가는 경로의 개수를 O(NM)으로 구할 수 있다.

세 번째로는 간단한 조합론을 통해 경로의 개수를 할 수 있다. 1번 칸에서 NM 번 칸으로 가려면 순서에 상관없이 오른쪽 방향으로 M-1번, 아래 방향으로 N-1번 이동하면 된다.

결국 1번 칸에서 NM 번 칸으로 가는 경로의 수는 오른쪽 이동 M-1 개와 아래쪽 이동 N-1 개의 순서를 섞는 경우의 수로 이 된다. 계산 중 숫자가 int 나 long long의 정수 표현 범위를 넘어가지 않도록 곱셈과 나눗셈의 위치를 잘 조절하면 모든 경우에 옳은 답을 출력한다.

K ≠ 0인 경우에는 중간에 꼭 K를 들러야 하므로 (1번 칸에서 K번 칸으로 가는 모든 경로 의 수) * (K번 칸에서 NM 번 칸으로 가는 모든 경로의 수) 가 답이 된다. 위의 세가지 방법 중 하나로 1번 칸에서 특정 칸으로 이동하는 경우의 수를 모두 구하면 K ≠ 0인 경우 K 번 칸의 위치를 (Y,X)라 했을 때 답은 Dy,x × Dn-y+1,m-x+1 이 된다.