测试数据来自 system/3020

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有 2 行 \(N\) 列的长方形，准备用 \(1×2\) 的骨牌取铺满。但有些地方已经铺了一些骨牌，只需要把剩下的地方铺满即可，请问有多少种不同的铺法？

【输入格式】

　　第一行包含两个整数 \(N\) 和 \(M\)，表示长方形有N的列数，且已经铺好了M块骨牌。
　　接下来的 \(M\) 行，每行两个整数 \(t\) 和 \(k\)，当 \(t=0\) 时，表示该骨牌是竖着放在从左数起的第 \(k\) 列上；当 \(t=1\) 时，表示该骨牌是横着放在从左数起的第 \(k，k+1\) 列上，且是上面的一行。
　　输入数据保证合法。　　

【输出格式】

　　输出一个整数，表示方案总数，这个数可能很大，所以只需输出模 1234567 后的结果。

【输入输出样例】

　Input

10 2
0 4
1 7

　Output

12

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤1000\)，\(1≤M≤10\)。

【来源】

　　Mr.he