Tray Bien

André Claude Marzipan is the head chef at the French restaurant Le Chaud Chien. He owns a vast number of baking trays, which come in two sizes: 1 foot by 1 foot, and 1 foot by 2 feet. He stores them along 3-foot deep shelves of various lengths. For example, on a shelf that is 5 feet long, he might store baking trays in either of the two ways shown below:

Of course, there are many more than just these two ways, and in his off hours, André often wonders how many different ways he can place trays on a given shelf. André is a bit of un maniaque du rangement (neat freak), so he insists that the trays are always aligned along the two axes defined by the shelf edges, that the edges of the trays are always 1 foot multiples away from any edge, and that no portion of a tray extends beyond the shelf. The matter is complicated by the fact that often there are locations on the shelf where he does not want to put any baking trays, due to leaks above the shelf, dents in the shelf's surface, etc. Since André is more adept at cuisine than counting, he needs a little help.

Input Specification

The input contains several test cases. Each test case consists of two lines: the first line will contain two integers m and n, where 1 ≤ m ≤ 24 indicates the length of the shelf (which is always 3-feet deep), and n indicates the number of bad locations on the shelf. The next line will contain n coordinate pairs, each composed of x and y, indicating the locations where trays should not be placed, where 0 < x < m and 0 < y < 3. No location will have integer coordinates, and coordinates are specified to the nearest hundredth. If n = 0, this second line will be blank.

Output Specification

For each test case, output the number of ways that trays could be placed on the shelf, on a line by itself.

Sample Input

1. 4 0
3. 4 2
4. 0.29 2.44 2.73 1.8

download as text file

Output for Sample Input

1. 823
2. 149

download as text file