有一个的棋盘,现在棋盘中有很多地雷标记,如果走到地雷的上下左右或者地雷本身所在的格子都会触发地雷爆炸,视为失败。
请问从棋盘的左上方走到右下方有多少种安全的走法。结果可能会很大,结果请对 取余。
输入有行
第一行三个整数,表示在的棋盘中有个地雷
后行,每行两个整数,表示地雷的坐标
一个整数,表示安全路径的方案数
样例输入
6 6 2 3 3 3 4
样例输出
13