1222: 方案数

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：1 Solved：1

Description

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


Input

第1行输入两个正整数N、M（1<N、M<20）。N表示三角形的层数，M表示“陷阱”的个数。

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

Output

小球从上到下的方案数。

Sample Input Copy 

 4 1
 3 2

Sample Output Copy 

4

HINT

1<N、M<20