ABPerm

#include<fstream>
#define MOD 1000000007
using namespace std;
ifstream fi("abperm.in");
ofstream fo("abperm.out");
int n,rez,i,tip,dr,A[100005],B[100005],PozA[100005],PozB[100005],Nr[100005],Good[100005];
int Fact[100005],I[100005];

int pu(int a, int b)
{
    int rez=1,i;
    for(i=0; (1<<i)<=b; i++)
    {
        if((1<<i)&b)
            rez=(1LL*rez*a)%MOD;
        a=(1LL*a*a)%MOD;
    }
    return rez;
}

int comb(int n, int k)
{
    int rez=(1LL*Fact[n]*I[n-k])%MOD;
    rez=(1LL*rez*I[k])%MOD;
    return rez;
}

int main()
{
	fi>>tip>>n;
	for(i=1; i<=n; i++)
    {
        fi>>A[i];
        PozA[A[i]]=i;
    }
    for(i=1; i<=n; i++)
    {
        fi>>B[i];
        PozB[B[i]]=i;
    }
    Fact[0]=1;
    for(i=1; i<=n; i++)
        Fact[i]=(1LL*Fact[i-1]*i)%MOD;
    I[n]=pu(Fact[n],MOD-2);
    for(i=n-1; i>=0; i--)
        I[i]=(1LL*(i+1)*I[i+1])%MOD;
    dr=n+1;
    for(i=0; i<=n; i++)
    {
        if(i>0)
            dr=min(dr,PozB[A[i]]);
        if(n-i<dr)
        {
            rez=(1LL*rez+comb(n,i))%MOD;
            Good[i]=1;
        }
    }
    if(tip==2)
    {
        for(i=1; i<=n; i++)
            Nr[i]=1;
        for(i=n-1; i>=1; i--)
            if(A[i+1]==B[PozB[A[i]]+1])
                Nr[A[i]]=1+Nr[A[i+1]];
        for(i=1; i<=n; i++)
            if(Good[PozA[i]-1] && PozA[i]+PozB[i]-2<n && Nr[i]+PozA[i]+PozB[i]-2>=n)
                rez=(1LL*rez-1LL*comb(PozA[i]+PozB[i]-2,PozA[i]-1)+1LL*MOD)%MOD;
    }
	fo<<rez<<'\n';
	fi.close();
    fo.close();
    return 0;
}