[ABC357] G - Stair-like Grid

G - Stair-like Grid

Time Limit: 6 sec / Memory Limit: 1024 MB

分数: 650 分

题面

有一个特殊的网格，有 行。( 为偶数.) 从顶部往下看，第 行从左边算起有 个单元格。
例如，当 时，网格看起来像下面这样：

记 为网格中从顶部往下数第 行，从左往右数第 列的单元格。
每个单元格可以是空单元格或者墙单元格。共有 个墙单元格，第 个墙单元格是 。这里， 和 是空单元格。
从 开始，有多少种方法可以通过重复向右或向下移动到相邻的空单元格达到 ？找到对 取模后的计数。

限制条件

• 是偶数.
• 并且 .
• 若 ，则 .
• 所有输入值均为整数。

---

输入

输入以以下格式从标准输入中给出：

输出

打印出从 开始，通过重复向右或向下移动到相邻的空单元格达到 的方法数，对 取模。

---

输入样例 1

4 2
2 1
4 2

输出样例 1

2

满足条件的两条路径如下：

---

输入样例 2

6 3
2 1
3 3
4 2

输出样例 2

0

---

输入样例 3

100 10
36 9
38 5
38 30
45 1
48 40
71 52
85 27
86 52
92 34
98 37

输出样例 3

619611437

---

输入样例 4

100000 10
552 24
4817 255
7800 954
23347 9307
28028 17652
39207 11859
48670 22013
74678 53158
75345 45891
88455 4693

输出样例 4

175892766