CSP后的第一篇题解。
不知道为啥突然很想刷容斥，于是用容斥题进行康复训练。
定义$f(n,m)$为从$(1,1)$走到$(n,m)$（没有障碍）的方案数，强制$n<m$，反正$f(n,m)=f(m,n)$。
如果只有$\rightarrow$和$\uparrow$就是$C_{n+m}^n$。
有了$\nearrow$就枚举有多少步走$\nearrow$，得出$f(n,m)=\sum\limits_{i=0}^nC_{n+m-i}^iC_{n+m-2i}^{n-i}$
根据$C_m^rC_{m-r}^{n-r}=C_m^nC_n^r$还可以把这个式子变得更漂亮些：$f(n,m)=\sum\limits_{i=0}^nC_{n+m-i}^nC_n^i$。
很妙的一个结论是走出边界的方案数实际上就是走到$(n+1,m+1)$的方案数，因为一旦走出边界，到$(n+1,m+1)$的方案就是唯一的了。
把障碍点以$x$为第一关键字、$y$为第二关键字排序。枚举障碍点集合$S$，记$g(S)$为从$(1,1)$经过$S$中所有点到达$(n+1,m+1)$的方案数。
显然$g(S)$就是按顺序的相邻两点、$(1,1)$到第一个点和最后一个点到$(n+1,m+1)$围成的矩形的$f$乘积。如果存在一个点在上一个点的右下方，方案数就为$0$。
$O(mk^2\log_{mod}n)$预处理出障碍点两两之间矩形的$f$值，$\log_{mod}$是卢卡斯带的。
最后容斥，答案为$\sum\limits(-1)^{|S|}g(S)$。
复杂度$O(mk^2\log_{mod}n+k2^k)$。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 100005
#define inf 0x3f3f3f3f
const int mod = 59393;
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int fac[mod]={1},inv[mod],f[21][21],g[21];
int INV(int x){return x==1?1:1ll*(mod-mod/x)*INV(mod%x)%mod;}
struct fpos{
int x,y;
bool operator < (const fpos &X)const{
if(x!=X.x)return x<X.x;
return y<X.y;
}
}p[21];
inline int C(int n,int m){
if(m>n)return 0;
if(n>=mod)return 1ll*C(n/mod,m/mod)*C(n%mod,m%mod)%mod;
return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
inline int calc(int n,int m){
if(n>m)swap(n,m);
int ans=0;
for(register int i=0;i<=n;++i)(ans+=1ll*C(n+m-i,n)*C(n,i)%mod)%=mod;
return ans;
}
inline int pow1(int x){return x&1?-1:1;}
inline int pop_count(int x){
int ans=0;
while(x)++ans,x-=x&-x;
return ans;
}
int main(){
for(register int i=1;i<mod;++i)fac[i]=1ll*fac[i-1]*i%mod;
inv[mod-1]=INV(fac[mod-1]);
for(register int i=mod-2;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
int n=read(),m=read(),k=read(),ans=0;
for(register int i=1;i<=k;++i)p[i].x=read(),p[i].y=read();
sort(p+1,p+1+k),p[0].x=1,p[0].y=1;
for(register int i=0;i<=k;++i){
f[i][i]=1,g[i]=calc(n+1-p[i].x,m+1-p[i].y);
for(register int j=i+1;j<=k;++j){
if(p[j].y<p[i].y)continue;
f[i][j]=calc(p[j].x-p[i].x,p[j].y-p[i].y);
}
}
for(register int i=0;i<1<<k;++i){
int last=0,res=1;
for(register int j=1;j<=k;++j)
if(i>>j-1&1)res=1ll*res*f[last][j]%mod,last=j;
res=1ll*res*g[last]%mod;
ans=(ans+pow1(pop_count(i))*res)%mod;
}
printf("%d\n",(ans+mod)%mod);
}
