[HNOI2019]多边形

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long int
#define mod 1000000007
inline int mul(int a,int b){return (int)((ll)a*b%mod);}
inline int pow(int a,int b)
{
    int res=1;
    while(b>0){
        if(b&1)
            res=mul(res,a);
        b>>=1;
        a=mul(a,a);
    }
    return res;
}
inline int inv(int x){return pow(x,mod-2);}
inline int _abs(int x){return x>0?x:-x;}

int n,m,k,T,ans=1,cnt=0;
int fac[100001],invfac[100001];
inline int modn(int x)
{
    if(x<0) return x+n;
    if(x>=n) return x-n;
    return x;
}
inline int C(int a,int b)
{
    return mul(mul(fac[a],invfac[b]),invfac[a-b]);
}
inline int invC(int a,int b)
{
    return mul(mul(invfac[a],fac[b]),fac[a-b]);
}
struct edge{
    int a,b,d1,d2,in,out;
}ed[400000];
int st[100001];
inline bool comp(edge e1,edge e2)
{
    if(e1.a==e2.a)
        return modn(e1.b-e1.a)<modn(e2.b-e2.a);
    return e1.a<e2.a;
}
inline int find(int x,int y)
{
    y=modn(y-x);
    int l=st[x],r=st[x+1]-1,mid;
    while(l<r){
        mid=(l+r)>>1;
        if(modn(ed[mid].b-x)<y)
            l=mid+1;
        else r=mid;
    }
    return l;
}

void read(void)
{
    scanf("%d%d",&T,&n);
    k=n+n-6;
    for(int i=n-4;i>=0;i--){
        scanf("%d%d",&ed[i].a,&ed[i].b);
        ed[i].a%=n; ed[i].b%=n;
        ed[k-i-1].a=ed[i].b;
        ed[k-i-1].b=ed[i].a;
    }
    for(int i=0;i<n;i++){
        ed[k].a=i; ed[k++].b=modn(i+1);
        ed[k].b=i; ed[k++].a=modn(i+1);
    }
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=mul(fac[i-1],i);
    invfac[n]=inv(fac[n]);
    for(int i=n-1;i>=0;i--)
        invfac[i]=mul(invfac[i+1],i+1);
    sort(ed,ed+k,comp);
    int pos=0;
    for(int i=0;i<=n;i++){
        st[i]=pos;
        while(pos<k&&ed[pos].a==i)
            pos++;
    }
    int p,q;
    for(int i=0;i<n;i++)
        for(int j=st[i]+1;j<st[i+1];j++){
            p=ed[j].b; q=ed[j-1].b;
            if(p>q) swap(p,q);
            if(p<i&&i<q)
                ed[find(p,q)].out=ed[find(q,p)].out=i;
            else ed[find(p,q)].in=ed[find(q,p)].in=i;
        }
    return;
}

void dfs(int id)
{
    if(_abs(ed[id].a-ed[id].b)==1){
        ed[id].d1=0; ed[id].d2=1;
        return;
    }
    int p=find(ed[id].a,ed[id].out),q=find(ed[id].b,ed[id].out);
    int r=find(ed[id].b,ed[id].a);
    dfs(p); dfs(q);
    ed[id].d1=ed[r].d1=ed[p].d1+ed[q].d1+1;
    ed[id].d2=ed[r].d2=mul(mul(ed[p].d2,ed[q].d2),C(ed[id].d1-1,ed[p].d1));
    return;
}

int main(void)
{
    read();
    for(int i=st[0]+1;i<st[1];i++){
        int t=find(ed[i-1].b,ed[i].b);
        dfs(t);
        cnt+=ed[t].d1;
        ans=mul(ans,mul(C(cnt,ed[t].d1),ed[t].d2));
    }
    if(T==0) printf("%d\n",cnt);
    else printf("%d %d\n",cnt,ans);
    int p,q,r,a1,a2,t1,t2,A,B,C;
    scanf("%d",&m);
    while(m--){
        scanf("%d%d",&p,&q);
        r=find(p,q);
        if(ed[r].in==0){
            a1=cnt-1;
            a2=mul(inv(cnt),ed[r].d1);
        }
        else{
            a1=cnt;
            A=find(p,ed[r].out); B=find(q,ed[r].out);
            t1=find(p,ed[r].in); t2=find(q,ed[r].in);
            if(ed[t1].d1<ed[t2].d1)
                C=t1;
            else C=t2;
            a2=mul(inv(ed[B].d1+ed[C].d1+1),ed[A].d1+ed[B].d1+1);
        }
        if(T==0) printf("%d\n",a1);
        else printf("%d %d\n",a1,mul(ans,a2));
    }
    return 0;
}