忍者少女永不停歇

没事没事。往前走，总会有办法的！

宅邸内部由网格构成。如下方泉奈画的图所示，从上往下第 $i$ 行的第 $1$ 列到第 $i-1$ 列是正方形格子，第 $i$ 列是等腰直角三角形格子！除三角形的斜边外，每个格子的各条边长都为 $1$！

• 下降（↓）：向下移动一格。也就是说，若当前位置为 $(x, y)$，则移动到 $(x, y - 1)$。
• 闪避（→）：向右移动一格。也就是说，若当前位置为 $(x, y)$，则移动到 $(x + 1, y)$。

这样一来……只需要考虑总移动次数为 $N$ 的路径！而且不能走出宅邸，所以移动过程中必须始终位于三角形内部或边界上。

可是，宅邸里有可怕的陷阱！根据泉奈收集到的情报，移动时必须满足以下所有条件！

• 对于 $1 \le i \le M$，第 $k_i$ 次移动时，泉奈所在位置的陷阱会启动。为了避开陷阱，必须在这次移动中执行第 $c_i$ 次闪避（→）。

也就是说，第 $k_i$ 次移动必须是闪避（→），而且必须是整条路径中的第 $c_i$ 次闪避（→）！当然，泉奈可是忍者，即使没有陷阱也可以闪避（→）！

宅邸里有许多通往终点的岔路，掌握所有满足条件的路线十分重要！让我们求出泉奈可以选择的路径有多少条吧！忍忍！

接下来的 $M$ 行，每行给出以空格分隔的 $k_i$、$c_i$。$(1 \le k_i \le N$; $k_i < k_{i + 1}$; $1 \le c_i \le \frac{N}{2}$; $c_i < c_{i + 1})$

时间限制

1000 ms

内存限制

1024 MB

检查器

CUSTOM