小SYY学编程

题目描述:

小SYY刚刚学会BFS，她觉得很自（zhuang）豪（bi），可是，当她一转头，一道Dp题出现了在她的面前，她就懵（fa）逼（dian）了。于是，她找到了Dp特别牛逼的大佬——你！

SYY把题目简化后交给了你，你若做出来了，小SYY会给你10000000000000000000 mod 10元RMB呢！题目大意如下：

温州中学（一个m*n的矩阵）有很多果树，最大的果树在坐标（m，n）上，你在（1，1）上，可以上下左右移动。其中有许多（k个）障碍物，问到达终点有多少条路径？若没有，则输出0。

输入格式:

三个数：m，n，k，意义如题目

接下来第2行到第k+1行每行两个整数x，y，表示第x行第y列有障碍。

输出格式:

输出一个数out，表示总路径数，你可以确定这个数小于等于1887415157。

样例输入:

样例1：
2 3
1
2 1

样例2：
3 4
3
2 3
2 1
1 4

样例输出:

样例1：
2

样例2：
1

提示:

对于100%数据:m<=25,n<=25。

保证（1，1），（m，n）不会有障碍

时间限制: 1000ms
空间限制: 128MB

---

来源: by zhr