Limited Permutation

As to a permutation $p_1, p_2, \cdots, p_n$ from $1$ to $n$, it is uncomplicated for each $1 \leq i \leq n$ to calculate $(l_i, r_i)$ meeting the condition that $\min(p_L, p_{L + 1}, \cdots, p_R) = p_i$ if and only if $l_i \leq L \leq i \leq R \leq r_i$ for each $1 \leq L \leq R \leq n$.

Given the positive integers $n$, $(l_i, r_i)$ $(1 \leq i \leq n)$, you are asked to calculate the number of possible permutations $p_1, p_2, \cdots, 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$.

The input contains multiple test cases.

For each test case:

The first line contains one positive integer $n$, satisfying $1 \leq n \leq 10^6$.

The second line contains $n$ positive integers $l_1, l_2, \cdots, l_n$, satisfying $1 \leq l_i \leq i$ for each $1 \leq i \leq n$.

The third line contains $n$ positive integers $r_1, r_2, \cdots, r_n$, satisfying $i \leq r_i \leq n$ for each $1 \leq i \leq n$.

It's guaranteed that the sum of $n$ in all test cases is not larger than $3 \cdot 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.

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.

3
1 1 3
1 3 3
5
1 2 2 4 5
5 2 5 5 5

Case #1: 2
Case #2: 3

2017 Multi-University Training Contest - Team 1