따로 걸어가기
시간 제한1초메모리 제한1024 MB
두 사람이 (1,1)에서 (N,M)까지 오른쪽이나 아래로만 이동하며, 시작과 도착을 제외하고 같은 칸에서 만나지 않는 경우의 수를 구합니다.
문제
토끼 부부 토순이와 토준이는 크게 싸운 뒤 집까지 따로 걸어가려고 한다.

토순이와 토준이는 행 열의 2차원 격자 위에서 움직이며, 오른쪽과 아래쪽으로만 움직일 수 있다.
를 에서 아래쪽으로 칸, 오른쪽으로 칸 움직인 위치라고 하자.
부부는 에서 출발하여 동시에 한 칸씩 움직이며 에 있는 집까지 간다.
이 과정에서 출발점과 도착점(집)을 제외하고, 중간에 같은 칸에서 만나지 않으려 한다.

부부가 집까지 걸어가는 방법의 수를 구하라.
입력
첫째 줄에 정수 과 이 공백을 사이에 두고 주어진다. ()
출력
부부가 집까지 걸어가는 방법의 수를 로 나눈 나머지를 출력한다. (은 소수이다.)