# HDU 6044 Limited Permutation

/ 0评 / 0

##### 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.

• 默认
• 护眼
• 夜晚
• Serif
• Sans