시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 761 168 103 22.940%

문제

세준이는 크기가 N*M인 직사각형 도시에 살고 있다.

또, 세준이의 집은 1,1에 있고, 학원은 N,M에 있다. 또, 이 도시에는 오락실이 C개 있다.

세준이는 항상 위 또는 오른쪽으로만 이동할 수 있다. 다른 말로 하면 현재 위치가 (x,y) 일 때, (x+1, y) 또는 (x,y+1)로만 이동할 수 있다. 또, 세준이가 오락실을 잠깐 들릴 때는 규칙이 하나 있는데, 오락실 번호는 반드시 증가하는 순서대로 가야한다. 다시말하면, 2번 오락실을 먼저 가고, 그 후에 1번 오락실을 가면 안된다. 2번 오락실을 가려면, 그 전에 아무 오락실도 가지 않거나, 1번 오락실을 들렸을 때만 가능하다.

세준이는 오락실을 K번 들려서 학원에서 도착하는 경로의 경우의 수가 궁금해지기 시작했다.

오락실을 0개 들렸을 때부터, C개 들렸을 때 까지 경우의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N M C가 주어진다. N과 M과 C는 50보다 작거나 같은 자연수이다. 둘째 줄부터 K개의 줄에 1번 오락실부터 C번 오락실까지 위치가 차례대로 주어진다. 오락실의 위치가 중복되는 경우는 없지만, 오락실의 위치가 (1,1) 또는 (N,M)일 수도 있다.

출력

첫째 줄에 0개 들렸을 때, 1개 들렸을 때, ..., C개 들렸을 때 총 경로의 개수를 한 줄에 공백을 사이에 두고 출력한다. 경로의 개수는 1000007로 나눈 나머지를 출력한다.

예제 입력

3 3 2
2 2
3 2

예제 출력

1 3 2

힌트

0개 (1,1)->(1,2)->(1,3)->(2,3)->(3,3)

1개 (1,1)->(2,1)->(2,2)->(2,3)->(3,3) (1,1)->(1,2)->(2,2)->(2,3)->(3,3) (1,1)->(2,1)->(3,1)->(3,2)->(3,3)

2개 (1,1)->(2,1)->(2,2)->(3,2)->(3,3) (1,1)->(1,2)->(2,2)->(3,2)->(3,3)

출처