#230. 机器人走方格
机器人走方格
Background
zjz非常喜欢机器人,因此他举办了一个机器人参加走方格大赛。
Description
在一个 的场地中,你的机器人起点位于左上角,终点为右下角。场地中有一些位置有障碍物,不能走有障碍物的位置。
由于要快速到达终点,他给他的机器人设定了一个限制,只能往下走或往右走;同时,他也给他的机器人增加了一个好玩的设定,就是每一步都由机器人自己随机选择往下或往右。
请你计算出这种情况下他的机器人一共有多少种走到终点的走法。
由于答案可能很大,因此你的答案需对取模。
Format
Input
一行输入两个整数 和 ,表示场地的大小。
接下来一行输入一个整数 ,表示场地有 个障碍物。
接下来 行每行输入两个整数 ,表示在 位置有一个障碍物。
Output
输出一个整数,表示机器人的走法对取模的结果。
Samples
2 2
1
2 0
5