##### Multi-University Training Team 1-1012虚建笛卡尔树

Time Limit: 4000/2000 MS (Java/Others)

As to a permutation $p_1,p_2,⋯,p_n$ from $1$ to $n$, it is uncomplicated for each $1≤i≤n$ to calculate $(l_i,r_i)$ meeting the condition that $min(p_L,p_{L+1},⋯,p_R)=pi$ if and only if $l_i≤L≤i≤R≤r_i$ 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 $p_1,p_2,⋯,p_n$ 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 $10^9+$7.

#### Input:

The input contains multiple test cases.
For each test case:
The first line contains one positive integer $n$, satisfying $1≤n≤10^6$.
The second line contains $n$ positive integers $l_1,l_2,⋯,l_n$, satisfying $1≤l_i≤i$ for each$1≤i≤n$.

The third line contains n positive integers $r_1,r_2,⋯,r_n$, satisfying $i≤r_i≤n$ for each $1≤i≤n$.

It’s guaranteed that the sum of n in all test cases is not larger than $3⋅10^6$.

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.

#### Output :

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.

[cpp]
3
1 1 3
1 3 3
5
1 2 2 4 5
5 2 5 5 5
[/cpp]

[cpp]
Case #1: 2
Case #2: 3
[/cpp]

#### Code

[cpp]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = ll(1e9+7);
namespace fastIO {
#define BUF_SIZE 100000
bool IOerror = 0;
inline char nc() {
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
if(p1 == pend) {
p1 = buf;
pend = buf + fread(buf, 1, BUF_SIZE, stdin);
if(pend == p1) {
IOerror = 1;return -1;
}
}
return *p1++;
}
inline bool blank(char ch) {
return ch == ‘ ‘ || ch == ‘\n’ || ch == ‘\r’ || ch == ‘\t’;
}
char ch;
while(blank(ch = nc()));
if(IOerror)return;
for(x = ch – ‘0’; (ch = nc()) >= ‘0’ && ch <= ‘9’; x = x * 10 + ch – ‘0’);
}
#undef BUF_SIZE
};
using namespace fastIO;
const int maxn = int(1e6+7);
struct seg{
ll l,r,id;
}a[maxn];
bool cmp(const seg &a, const seg &b) {
return a.l==b.l?a.r>b.r:a.l<b.l;
}
ll jc[maxn];
ll power(ll x,ll n) {//此处用费马小定理处理逆元
ll ret =1;
while(n) {
if(n&1) ret = ret * x % mod;
x = x * x % mod;
n>>=1;
}
return ret;
}
bool mark;
ll cnt;

ll C(ll n,ll m) {//计算组合数 n>=m
ll ret=1;
if(n==m) return 1;
ret = ret * jc[n] power(jc[m]jc[n-m]%mod,mod-2) % mod;
return ret;
}
ll dfs(ll l,ll r) {
if(l>r) return 1LL;
seg now = a[cnt++];
if(now.l != l || now.r != r || mark) {
mark=1;
return 0LL;
}
if(l==r) return 1LL; //res = f(v1)f(v2)C(sz(v1),sz(v1)+sz(v2))
ll res = C(now.r-now.l, now.id-now.l)dfs(now.l, now.id-1)%mod;
res = res *dfs(now.id+1, now.r)%mod;
return res;
}
int main() {
ll n;int kase=1;
jc[0]=1;
for(int i=1;i<maxn;i++) jc[i]=jc[i-1]
(ll)i%mod;