Xtreme Driving
Alice, one of the IEEEXtreme participants, is on her way to her university to take part in this year’s contest. To get to the university she has to drive on a four lane highway, but as the highway is very long she quickly becomes bored. She decides to practice for the contest by thinking about some problems related to the highway she’s driving on. She comes up with the following problem:
Let’s say that, in a single unit of time, her car, which is of unitlength, can perform one of the following three actions:

Drive one unit forward, staying in the same lane

If the car is not on the leftmost lane, drive one unit forward and switch to the lane on the left

If the car is not on the rightmost lane, drive one unit forward and switch to the lane on the right
If the highway is $K$ units in length, in how many ways is it possible to drive through the highway, provided that she starts on the first unit of the highway at the leftmost lane, and ends at the last unit of the highway, also at the leftmost lane?
As she’s been training very hard for the contest, it doesn’t take her long to come up with a solution to this problem. But all of a sudden, out of nowhere, a large cow appears in front of her car, and she just barely manages to avoid crashing into it. She got a bit too distracted thinking about the problem... But this incident gives her an idea: what if the highway had a set of stationary cows that the car must avoid crashing into?
Unfortunately she doesn’t have time to think about this version of the problem as she just arrived at the university and the contest is about to start. When the contest starts, she is very surprised to see that the problem she was thinking about is just like one of the problems presented in the contest. What a coincidence! Again her hard practice pays off and she quickly solves the problem. But the real question is, can you?
Input
Input begins with a line containing two integers, $K$, the length of the highway, and $N$, the number of cows standing on the highway, subject to the following constraints:
$2 \leq K \leq 10^{18}$
$0 \leq N \leq 100$
$N \leq 4(K  2)$
Then follow $N$ lines. The $i^{th}$ line contains two integers describing the location of the $i^{th}$ cow, $x_ i$, the lane on which the cow is standing (1 being the leftmost, and 4 being the rightmost), and $y_ i$, the unit on which the cow is standing, subject to the following constraints:
$1 \leq x_ i \leq 4$
$1 < y_ i < K$
Notice that no cows are on the first or last unit of the highway. It is also guaranteed that no two cows share the same position.
Output
You are to output the number of ways to drive from the leftmost lane at the first unit of the highway to the leftmost lane at the $K^{th}$ unit of the highway subject to the rules described above, and the additional constraint that the car must not drive to a position occupied by a cow.
As the number of ways can be quite large, please output the answer modulo $10^9 + 7$. Note that this is the same as the remainder when dividing the number of ways by $10^9 + 7$.
Explanation of Sample Input
In this example there are three ways to drive through the highway, and they are shown in the following figures. Notice that the car can drive in between cows (as long as other driving rules are fulfilled), but it must not drive to a unit occupied by a cow.
Sample Input 1  Sample Output 1 

7 5 1 4 1 6 2 2 2 3 3 5 
2 
Sample Input 2  Sample Output 2 

9 7 1 6 2 3 2 5 2 7 3 4 3 5 4 4 
15 