오락실 순서 경로 찾기
시간 제한2초메모리 제한128 MB
(1,1)에서 (N,M)까지 우측 또는 아래로만 이동하는 경로 중 지나는 오락실 번호가 항상 증가하는 경로만 유효하다고 볼 때, 방문한 오락실 개수별 경로 수를 구하는 문제입니다.
문제
크기가 N * M인 격자 도시가 있습니다. 집은 (1, 1)에 있고 목적지는 (N, M)에 있습니다. 도시에는 번호가 1번부터 C번까지 붙은 오락실 C개가 있습니다.
현재 위치가 (r, c)이면 (r + 1, c) 또는 (r, c + 1)로만 이동할 수 있습니다. 즉, 아래쪽이나 오른쪽으로만 이동합니다.
경로가 오락실을 지나갈 때는 방문한 오락실 번호가 strictly increasing 해야 합니다. 예를 들어 2번 오락실을 방문한 뒤에는 1번 오락실을 방문할 수 없습니다. 반대로 2번 오락실은 그 전에 아무 오락실도 방문하지 않았거나 1번 오락실을 방문한 뒤에만 방문할 수 있습니다.
오락실을 정확히 K개 방문하면서 집에서 목적지까지 가는 경로의 수를 구하려고 합니다. K = 0, 1, ..., C에 대해 각각의 경로 수를 출력하세요.
입력
첫째 줄에 N M C가 주어집니다. N과 M은 50 이하의 자연수이고, C는 0 이상 50 이하의 정수입니다.
다음 C개의 줄에는 1번 오락실부터 C번 오락실까지의 위치가 차례대로 주어집니다. 오락실 위치는 서로 중복되지 않습니다. 오락실은 (1, 1) 또는 (N, M)에 있을 수도 있습니다.
출력
첫째 줄에 오락실을 0개, 1개, ..., C개 방문하는 경로의 수를 공백으로 구분해 출력합니다.
각 경로의 수는 1,000,007로 나눈 나머지를 출력합니다.