Description

QQ 在演练期间，回忆起他所在城市在疫情严重期间，个别小区进行了封闭式管理，许多路口都封道的情形。他想起以前做过的一道题再加以变化，就形成了一道新题：
疫情期间医生开车上班
医生所在的城市街道好像一个棋盘，有 a 条南北方向的街道和 b 条东西方向的街道。南北方向 a 条街道从西到东依次编号为 1 到 a，而东西方向的 b 条街道从南 到北依次编号为 1 到 b，南北方向的街道 i 和东西方向的街道 j 的交点记为（i,j）。
假定医生家住在（1，1）处，而医院在（a,b）处，医生开车去上班，只能沿着街道走，而且为了缩短时间只允许沿着东、北方向行驶。现在有 n 个交叉路口，由于疫情交通管制，（X1,Y1）,(X2,Y2),(Xn,Yn),这些路口暂时不能通车。问医生上班有多少种走法？

Input Format

共二行。 
第一行包含两个整数 a 和 b，并且满足 1≦a，b≦16. 
第二行包含一个整数 n，表示有 n 个路口交通管制，不能行驶（1≦N≦40）。 
接下来的 n 行，每行两个整数 X_i、Y_i,描述路口的位置。

Output Format

输出一个整数，表示医生从（1，1）到（a，b）的上班路线总数。 

5 4
3
2 2 
2 3
4 2

5

Hint

Source

深搜