链接:https://www.luogu.org/problemnew/show/U45877#sub

桃园之礼(peach)

题目描述

小林和亮亮在桃园里一起玩游戏.桃园里的桃树成行成列,刚好构成一个N*M的矩阵,亮亮在某些桃树下面放置了一些小礼物,要求小林把所有树下的礼物全部收集起来.小林在左上角的桃树(1,1)出发,走到右下角的桃树(n,m).他只能沿着路经向下或向右走,某些桃树下有礼物,他必须到达所有的礼物的树下并把礼物收集起来.小林在出发前,想请你帮他计算一下,他有多少不同的走法.由于答案可能会很大,你只需要输出答案模100000000(10^8)后的值即可.

输入样例

第一行输入三个整数N,M.N,M表示矩阵的大小,K表示有礼物的桃树的颗数.

接下来k行,每行表示两个整数,X,Y,表示一颗有礼物的桃树的坐标(X,Y).

输出格式

只有一个整数,表示不同的走法模 100000000 后的值.

样例输入

5 4 1
2 2

样例输出

20

数据规模

对于 30% 的数据, 1 ≤ \leq ≤N , M ≤ \leq ≤ 30

对于100%的数据 , 1 ≤ \leq ≤ N,M ≤ \leq ≤ 30000,0 ≤ \leq ≤ K ≤ \leq ≤ 10000,1 ≤ \leq ≤ X ≤ \leq ≤ N,1 ≤ \leq ≤ Y ≤ \leq ≤ M.

题解:

code:

没写