Laying Tiles

During renovations at the Information Technology Laboratory, construction workers must replace damaged floor tiles in a laboratory corridor measuring 2 × n meters. The workers have an unlimited supply of tiles in two sizes: 1 × 2 meters and 1 × 1 meter. A 1 × 2 meter tile may be rotated 90 degrees before being laid and placed either along or across the corridor.

The workers have already begun the repairs and have laid k tiles of size 1 × 1 in some places on the corridor floor. To finish the repairs, the foreman needs to prepare a plan for the remaining work. To do this, he must decide how to lay tiles on the places where none have been laid yet. This can be done in various ways, and the foreman wants to go through all the options and choose the best one. Before doing so, the foreman wants to know how many options he will have to consider. This number must be found modulo 109 + 7.

Write a program that, given the corridor length n and the positions of the tiles already laid, determines the number of ways to lay tiles on the remaining places. The answer must be printed modulo 109 + 7.

The first line of the input file contains two integers: n, the length of the corridor, and k, the number of unit tiles already laid (1 ≤ n ≤ 100 000, 0 ≤ k < 2n).

The following k lines contain two integers each, xi and yi, which give the positions of the already laid unit tiles. The i-th tile is laid at the xi-th meter of the corridor in the yi-th row (1 ≤ xi ≤ n, 1 ≤ yi ≤ 2).

The output file must contain a single integer: the number of ways to lay tiles in the corridor, taken modulo 109 + 7.

Figure 1. All ways to lay tiles in the first example

Figure 2. All ways to lay tiles in the third example. An already laid tile is marked in gray.