被虐的体无完肤

今天考试那是一个惨啊，（其实就是我菜

T1：

Bob 来到了一个 $(x_i, y_i)(xi,yi)，保证没有两个豆子在同一个格子里，(1, 1)(1,1) 处和 (n, m)(n,m) 处没有豆子。$

Bob 从左上角

贪吃的 Bob 决定吃掉所有格子的豆子，他想知道是否存在多少条路径，使得他可以经过所有的豆子。由于答案很大，你只需要输出答案模 $10^9 + 7，109+7 的结果即可。$

输入输出格式

输入格式：

第一行三个整数

接下来 $x_i, y_i(1 leq x_i leq n, 1 leq y_i leq m)xi,yi(1≤xi≤n,1≤yi≤m)，意义如上所述。$

输出格式：

一行一个整数，表示答案。

输入输出样例

输入样例#1：复制

3 4 1
1 2

输出样例#1：复制

输入样例#2：复制

3 4 1
2 2

输出样例#2：复制

说明

对于 $30\%30% 的数据，满足 2 leq n, m leq 1002≤n,m≤100。$

对于 $60\%60% 的数据，满足 2 leq n, m leq 10002≤n,m≤1000。$

对于 $100\%100% 的数据，满足 2 leq n, m leq 10^5, 0 leq k leq min(n imes m - 2, 10^5)2≤n,m≤105,0≤k≤min(n×m−2,105)。$

设当前的位置为c(x,y),那么只能移动到c(x+1,y)或者c(x,y+1)所以先把豆子按x+y(所在对角线)的值排序

然后方案数= $\sum_{i=1}{}^nans*C({i,i+1})$

#include<bits/stdc++.h>
using namespace std;
#define re register int
#define ll long long
inline void FRE()
{
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}
inline void FCL()
{
    fclose(stdin);
    fclose(stdout);
}
priority_queue<int>mp;
vector<int>v;
const int N=2e5+5;
const int mod=1e9+7;
const int inf=0x3fffffff;
inline ll read()
{
    ll s=0,f=1;
    char a=getchar();
    while(a<'0'||a>'9')
    {
        if(a=='-')
        f=-1;
        a=getchar();
    }
    while(a>='0'&&a<='9')
    {
        s=(s<<3)+(s<<1)+a-48;
        a=getchar();
    }
    return s*f;
}
inline void output(ll x)
{
    ll y=10,len=1;
    while(y<=x)
    {
        y*=10;
        len++;
    }
    while(len--)
    {
        y/=10;
        putchar(x/y+48);
        x%=y;
    }
}
int n,m,k;
struct fuck
{
    int x;
    int y;
}poi[N];
inline bool cmp(fuck a,fuck b)
{
    return a.x+a.y<b.x+b.y;
}
int sum[N],num[N];
inline int work(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y%2==1)
        ret=1ll*ret*x%mod;
        x=1ll*x*x%mod;
        y/=2;
    }
    return ret;
}
inline void init(int t)
{
    sum[0]=num[0]=1;
    for(re i=1;i<=t;i++)
    {
        sum[i]=1ll*sum[i-1]*i%mod;
        num[i]=work(sum[i],mod-2)%mod;
    }
}
inline int C(int x,int y)
{
    return 1ll*sum[x]*num[y]%mod*num[x-y]%mod;
}
int main()
{
    //FRE();
    n=read(),m=read(),k=read();
    init(200000);
    for(re i=1;i<=k;i++)
    {
        poi[i].x=read(),poi[i].y=read();
    }
    poi[++k].x=n;
    poi[k].y=m;
    poi[++k].x=1;
    poi[k].y=1;
    sort(poi+1,poi+1+k,cmp);
    int ans=1;
    for(re i=2;i<=k;i++)
    {
        int x=poi[i].x-poi[i-1].x;
        int y=poi[i].y-poi[i-1].y;
        if(x<0||y<0)
        {
            ans=0;
            break;
        }
        ans=1ll*ans*C(x+y,x)%mod;
    }
    cout<<ans;
    //FCL();
    return 0;
}