Tray Bien

André Claude Marzipan is the head chef at the French restaurant Le Chaud Chien. He owns a great many baking trays, and they come in only two sizes, 1 foot × 1 foot and 1 foot × 2 feet. He stores them on shelves that are always 3 feet deep and vary in length. On a shelf 5 feet long, for example, he might store trays in either of the two ways shown below.

Figure G.1

There are many more ways than these two. André is un maniaque du rangement (a neat freak), so he always aligns the trays with the two axes given by the shelf edges, keeps every tray edge a whole number of feet from any shelf edge, and never lets a tray stick out past the shelf. A shelf $m$ feet long is therefore a grid of 1 foot squares with 3 rows and $m$ columns, and one tray covers either a single square or two squares that share an edge.

The matter is complicated by spots on the shelf where he does not want to put a tray, because of a leak above the shelf, a dent in the surface, and so on. A square that holds such a spot must be left empty, and every other square must be covered by exactly one tray. Trays of the same size are interchangeable, so two arrangements are different exactly when they pair squares into 1 × 2 trays differently.

André is more adept at cuisine than at counting. Find the number of ways the trays can be placed on the shelf.

The first line contains two integers $m$ and $n$. Here $m$ ($1 \le m \le 24$) is the length of the shelf, which is always 3 feet deep, and $n$ is the number of bad locations on the shelf.

The second line contains the $n$ coordinate pairs $x\ y$ of the locations where trays must not be placed. Every pair satisfies $0 < x < m$ and $0 < y < 3$, no coordinate is an integer, and coordinates are given to the nearest hundredth. If $n = 0$, the second line is empty.

Print the number of ways the trays can be placed on the shelf. The answer fits in a signed 64-bit integer.