택시 경로

그리드빌 마을의 도로망은 완전한 직사각형 격자다. 마을을 세운 사람들이 전산학자였던 터라 동서(EW) 방향과 남북(NS) 방향 모두 0번부터 번호를 붙였다. 동서로 뻗은 도로는 스트리트, 남북으로 뻗은 도로는 애비뉴라고 부른다.

한 택시 회사의 차고는 격자의 남서쪽 끝, 곧 0번 스트리트와 0번 애비뉴가 만나는 교차로에 있다. 차고에서 출발해 마을의 북동쪽 끝 교차로까지 가는 경로가 몇 개인지 구하라. 이동은 동쪽 또는 북쪽으로만 하며, 되돌아가지 않는다. 다만 공사 중이라 지나갈 수 없는 교차로가 섞여 있어 계산이 단순하지 않다.

경로의 수는 2147483647($2^{31}-1$)을 넘지 않는다.

입력은 여러 개의 지도로 이루어진다.

각 지도는 스트리트의 개수와 애비뉴의 개수를 나타내는 두 정수가 적힌 줄로 시작한다. 두 값 모두 1 이상 30 이하다. 그다음 줄부터는 지나갈 수 없는 교차로를 나타내는 정수 쌍이 한 줄에 하나씩 이어진다. 쌍의 첫 번째 값은 스트리트 번호, 두 번째 값은 애비뉴 번호다. 출발 교차로와 도착 교차로는 이 목록에 나오지 않는다. 한 지도의 입력은 0 0 쌍으로 끝난다. 전체 입력은 0 0이 적힌 줄이 하나 더 나오면 끝난다.

스트리트가 $S$개, 애비뉴가 $A$개인 지도에서 스트리트 번호는 $0$부터 $S-1$까지, 애비뉴 번호는 $0$부터 $A-1$까지다. 따라서 출발 교차로는 $(0, 0)$, 도착 교차로는 $(S-1, A-1)$이다.

지도마다 한 줄씩 다음 형식으로 출력한다.

Map <mapId>: <num>

<mapId>는 1부터 시작하는 지도 번호이고, <num>은 가능한 경로의 수다. <num>은 2147483647($2^{31}-1$)을 넘지 않는다.