图片被删除,或者路径改变
问题1492--梦萦 - 漫漫长夜

1492: 梦萦 - 漫漫长夜

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MiB

题目描述

临近二零二四年元旦夜,解衣欲睡,月色入户,欣然起行。念无与为乐者,遂觉漫漫长夜而难眠。Liji走至明月湖之桥,遇Belinra亦未寝,相与步于长桥。桥下如积水空明,听闻鸭鸭嘎叫。何夜无月?何处无跨年?但少闲人如他两人者耳。

现在Liji和Belinra的起点为(1,1),他们相与步在一个 n*m 的区域,每次可以向下或者向右走一格,但不巧的是白天天气异常,刚下过瓢泼大雨,他们相与步的区域有许多水洼。现在要求你求出他们在不踩水洼的条件下,相与步到(n,m)的位置一共有多少种走法。

其中给出你水洼的个数以及水洼的位置(xi,yi),数据保证(xi,yi)不是(n,m)点,并且已经走过的位置不能再走。

输入

输入占两行:

第一行三个整数n,m,k(1 ≤ n,m ≤ 1000,0 ≤ k ≤ min (1000,n*m) ),分别代表相与步区域的长度、宽度和水洼的数量

第二行到第 k + 1 行,分别代表每块水洼的位置(xi,yi),(1 ≤ xi ≤ n,1 ≤ yi ≤ m)

输出

输出一个整数,代表Liji与Belinra相与步从(1,1)走到(n,m)的走法可能性的总数量。由于答案可能很大,你需要把答案对 998244353 取模

特别地,如果他们无法相与步到(n,m)点,输出字符串 "What a Such long night! QwQ" 即可(输出不包含引号)

样例输入 Copy

3 4 3
1 3
3 1
3 3

样例输出 Copy

2

提示

样例所对应的区域如下:(X代表水洼,0代表可以相与步的路径)
0 0 X 0
0 0 0 0
X 0 X 0
能走到的一种可能性为:(1,1)->(1,2)->(2,2)->(2,3)->(2,4)->(3,4)
第二种可能性为:(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)