출근 경로
면접 대비시간 제한1초메모리 제한128 MB
서쪽 아래 (1,1)에서 동쪽 위 (w,h)로 동쪽과 북쪽으로만 이동하되, 연속한 교차로에서 방향을 두 번 바꾸지 않는 경로의 수를 100000으로 나눈 나머지를 구한다.
문제
상근이가 사는 도시에는 남북 방향 도로가 개, 동서 방향 도로가 개 있다.
남북 방향 도로에는 서쪽부터 차례대로 번이 매겨져 있고, 동서 방향 도로에는 남쪽부터 차례대로 번이 매겨져 있다. 서쪽에서 번째 남북 방향 도로와 남쪽에서 번째 동서 방향 도로가 만나는 교차로를 라고 하자.
상근이는 교차로 에 살고, 교차로 에 있는 회사까지 차로 출근한다. 차는 도로 위로만 움직일 수 있다. 회사에 최대한 빨리 도착하려고 상근이는 동쪽 또는 북쪽으로만 이동한다.
이 도시는 교통사고를 줄이기 위해, 교차로에서 방향을 바꾼 차가 바로 다음 교차로에서 다시 방향을 바꿀 수 없도록 정해 두었다. 즉, 한 번 방향을 바꾼 뒤에는 한 블록만 이동하고 곧바로 또 방향을 바꿀 수 없으며, 적어도 두 블록을 직진한 뒤에야 다시 방향을 바꿀 수 있다.
와 가 주어졌을 때, 상근이가 출근할 수 있는 서로 다른 경로의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 와 가 주어진다. ()
출력
첫째 줄에 상근이가 출근할 수 있는 경로의 개수를 으로 나눈 나머지를 출력한다.
힌트
교차로에서 방향을 바꾼 뒤에는 반드시 두 블록 이상 직진해야 다시 방향을 바꿀 수 있다. 다시 말해, 연이은 두 교차로에서 모두 방향을 바꿀 수는 없다. 예를 들어 , 인 경우 조건을 만족하는 경로는 모두 가지이다.