#6670. 递推5部曲:棋盘游戏-路径3 入门

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: zyl

题目描述

有一个的棋盘,现在棋盘中有很多地雷标记,如果走到地雷的上下左右或者地雷本身所在的格子都会触发地雷爆炸,视为失败。

请问从棋盘的左上方走到右下方有多少种安全的走法。结果可能会很大,结果请对 取余。

输入格式

输入有

第一行三个整数,表示在的棋盘中有个地雷

行,每行两个整数,表示地雷的坐标

输出格式

一个整数,表示安全路径的方案数

样例

样例输入

6 6 2
3 3
3 4

样例输出

13

数据范围与提示