暂无测试数据。

题目描述

有一个类似弹球的游戏，如下图，

小球从上向下滑落，
每次到一个“交叉”点都有2种选择：
向左或向右滑落。
如果有一个球从顶端滑落到底会有多少种方法?

特别是中间的“交叉”点有一些是“陷阱”，
小球滑到“陷阱”就不能再继续下滑了。

输入

第 1 行，输入两个正整数 \(N\)、\(M\)。
\(N\) 表示三角形的层数，\(M\) 表示“陷阱”的个数。

第 2 到 \(M+1\) 行：
每行 2 个整数 \(x\)、\(y\)，
表示第 \(x\) 行的第 \(y\) 个“交叉”点是“陷阱”。

输出

小球从上到下的方案数。

样例输入

4 1
3 2

样例输出

4

样例解释

数据范围限制

\(1 < N,M < 20\)

来源

基础篇例8.6