题目描述
临近二零二四年元旦夜,解衣欲睡,月色入户,欣然起行。念无与为乐者,遂觉漫漫长夜而难眠。Liji走至明月湖之桥,遇Belinra亦未寝,相与步于长桥。桥下如积水空明,听闻鸭鸭嘎叫。何夜无月?何处无跨年?但少闲人如他两人者耳。
现在Liji和Belinra的起点为(1,1),他们相与步在一个 n*m 的区域,每次可以向下或者向右走一格,但不巧的是白天天气异常,刚下过瓢泼大雨,他们相与步的区域有许多水洼。现在要求你求出他们在不踩水洼的条件下,相与步到(n,m)的位置一共有多少种走法。
其中给出你水洼的个数以及水洼的位置(xi,yi),数据保证(xi,yi)不是(n,m)点,并且已经走过的位置不能再走。
输入
输入占两行:
第二行到第 k + 1 行,分别代表每块水洼的位置(xi,yi),(1 ≤ xi ≤ n,1 ≤ yi ≤ m)
输出
特别地,如果他们无法相与步到(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)
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)