题目描述

希蒙是一位优秀的战地通讯员，现在有一个n*m的地图，如下图所示：希蒙要从地图左上角的1,1点出发，送一份情报到位于地图右下角n，m的营地去，中间进过一片雷区，一共有k枚敌人埋下的地雷，每个地雷都有紧挨其的上、下、左、右4个触发点，当希蒙处于地雷位置和其触发点位置时，地雷都会爆炸，并且炸毁处于地雷位置及其触发点位置的一切生物。问希蒙要将情报送到指定点一共有多少条路线，注意，希蒙只能向右走和向下移动。 上图左上角绿色点是出发点，右下角绿色点为终点，红色为地雷，橙色为地雷的触发点。

输入格式

共4行：

第一行三个整数 表示地图大小n和m，以及地雷数k

接下来k行，每行两个整数表示k枚地雷的位置

输出格式

一行一个整数，表示总共有多少种走法。结果可能非常巨大，请对125800取余。

样例

输入样例：

5 5 1
3 3

输出样例：

4

数据范围与提示

n,m均大于3，且不大于100 k不大于50