As to a permutation p1,p2,⋯,pn from 1 to n, it is uncomplicated for each 1≤i≤n to calculate (li,ri) meeting the condition that min(pL,pL+1,⋯,pR)=pi if and only if li≤L≤i≤R≤ri for each 1≤L≤R≤n.

Given the positive integers n, (li,ri) (1≤i≤n), you are asked to calculate the number of possible permutations p1,p2,⋯,pn from 1 to n, meeting the above condition.

The answer may be very large, so you only need to give the value of answer modulo 109+7.

 

The input contains multiple test cases.

For each test case:

The first line contains one positive integer n, satisfying 1≤n≤106.

The second line contains n positive integers l1,l2,⋯,ln, satisfying 1≤li≤i for each 1≤i≤n.

The third line contains n positive integers r1,r2,⋯,rn, satisfying i≤ri≤n for each 1≤i≤n.

It's guaranteed that the sum of n in all test cases is not larger than 3⋅106.

Warm Tips for C/C++: input data is so large (about 38 MiB) that we recommend to use fread() for buffering friendly.

size_t fread(void *buffer, size_t size, size_t count, FILE *stream); // reads an array of count elements, each one with a size of size bytes, from the stream and stores them in the block of memory specified by buffer; the total number of elements successfully read is returned.

 

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1 and y denotes the answer of corresponding case.

 

 

 

#include<bits/stdc++.h>

using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

typedef unsigned long long ULL;

const long long INF = 1e18+1LL;

const double pi = acos(-1.0);

const int N = 1e6+, M = 1e3+,inf = 2e9,mod = 1e9 + ;

namespace IO {

    const int MX = 4e7; //1e7占用内存11000kb

    char buf[MX]; int c, sz;

    void begin() {

        c = ;

        sz = fread(buf, , MX, stdin);

    }

    inline bool read(int &t) {

        while(c < sz && buf[c] != '-' && (buf[c] < '' || buf[c] > '')) c++;

        if(c >= sz) return false;

        bool flag = ; if(buf[c] == '-') flag = , c++;

        for(t = ; c < sz && '' <= buf[c] && buf[c] <= ''; c++) t = t *  + buf[c] - '';

        if(flag) t = -t;

        return true;

    }

}

const int MOD = (int)1e9 + ;

int F[N], Finv[N], inv[N];//F是阶乘，Finv是逆元的阶乘

void init(){

    inv[] = ;

    for(int i = ; i < N; i ++){

        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;

    }

    F[] = Finv[] = ;

    for(int i = ; i < N; i ++){

        F[i] = F[i-] * 1ll * i % MOD;

        Finv[i] = Finv[i-] * 1ll * inv[i] % MOD;

    }

}

inline LL C(int n, int m){//comb(n, m)就是C(n, m)

    if(m <  || m > n) return ;

    return F[n] * 1ll * Finv[n - m] % MOD * Finv[m] % MOD;

}

struct ss{

    int l,r,id;

    bool operator<(const ss& x) const{

        if(l == x.l) return r > x.r;

        else return l < x.l;

    }

}a[N];

int now,ok;

inline LL dfs(int ll,int rr) {

    if(!ok) return ;

    if(ll > rr) return 1LL;

    if(a[now].l != ll || a[now].r != rr) {

        ok = ;

        return ;

    }

    int ids = a[now++].id;

    return dfs(ll,ids-) * dfs(ids+,rr) % mod * C(rr-ll,ids-ll) % mod;

}

int main() {

    init();

    int cas = ,n;

    IO::begin();

    while(IO::read(n)) {

        for(int i = ; i <= n; ++i) IO::read(a[i].l);

        for(int i = ; i <= n; ++i) IO::read(a[i].r),a[i].id = i;

        now = , ok = ;

        sort(a+,a+n+);

        printf("Case #%d: %lld\n",cas++,dfs(,n));

    }

    return ;

}