뭐 어려운것도 아닌데 왜이렇게 오래걸린지..

get_value(int x_from, int y_from, int x_to, int y_to) 라는 함수를 작성하고

dp[i][j] : (x_from, y_from)부터 (x_to, y_to)까지 이동하는 경로의 수 라고 정의했습니다.

k가 0일때는 단순히 get_value(1, 1, N, M)을 출력해주고

k가 0이 아니면 new_N, new_M을 구해줘서 get_value(1,1,new_N, new.M) * get_value(new_N, new_M, N, M) 해주는데 이게 ㅎ...

주로 반례는 new_N 또는 new_M가 경계에 달라붙어있을 때 발생했습니다.. (new_N == 1 or new_M == 1 or new_N == N or new_M == M 일떄..)