题目描述

有一个类似弹球的游戏，如下图所示。 小球从上向下滑落，每次到一个“交叉”点都有2种选择：向左或向右滑落。如果有一个球从顶端滑落到底，有多少种不同的方法？但是中间的一个“交叉”点有一些“陷阱”，小球滑到“陷阱”就不能继续下滑了。

输入格式：

第1行输人两个正整数 N、M(1<N、M<20),N 表示三角形的层数，M 表示“陷阱”的个数；第 2 到 M+1行，每行 2 个整数 x、y,表示第 x 行的第 y 个“交叉”点是“陷阱”。

样例数据图示

输出格式：

小球从上到下的方案数。

样例：

4 1
3 2

4

Limitation

1s, 1024KiB for each test case.