Taxi Routes

The road network in the town of Gridville is a perfect rectangular grid. The founders of Gridville were computer scientists, so the grid is numbered starting from 0 in both the east-west (EW) and north-south (NS) directions. The roads running EW are called streets, and the roads running NS are called avenues.

A taxi company keeps its depot in the SW corner of the grid, at the intersection of 0th St and 0th Ave. Count how many routes reach the NE corner of the town. The taxi drives only eastward or northward, so no backtracking is allowed. Certain intersections are under construction and are therefore impassable. That complicates the count.

The number of routes never exceeds 2147483647 ($2^{31}-1$).

The input is a sequence of maps.

Each map begins with a line holding two integers, the number of streets and the number of avenues. Both values are between 1 and 30. The following lines hold pairs of integers naming the impassable intersections, one pair per line. The first element of a pair is the street number and the second is the avenue number. Neither the depot nor the destination appears on this list. The input for a single map ends with the pair 0 0. The input as a whole ends with one more line containing 0 0.

On a map with $S$ streets and $A$ avenues the street numbers run from $0$ to $S-1$ and the avenue numbers run from $0$ to $A-1$, so the depot is $(0, 0)$ and the destination is $(S-1, A-1)$.

For each map in the input, print one line in the following form.

Map <mapId>: <num>

Here <mapId> is the identification number of the map, an integer beginning from 1, and <num> is the number of routes available. <num> never exceeds 2147483647 ($2^{31}-1$).