For a permutation $p_1$, $p_2$, $\\dots$, $p_n$ obtained from $1$ to $n$, it is uncomplicated for each $i$ to calculate $(l_i, r_i)$ meeting the condition that $min (p_L, p_{L + 1}, \\dots, p_R) = p_i$ if and only if $l_i <= L <= i <= R <= r_i$.
Given the positive integers $n$, $(l_i, r_i)$, you are asked to calculate the number of possible permutations $p_1$, $p_2$, $\\dots$, $p_n$ obtained from $1$ to $n$, meeting the above condition.
The answer may be exceedingly large, so you should output the answer modulo $(10^9 + 7)$ instead.
The input contains multiple test cases.
For each test case, the first line contains an integer $n$ ($1 <= n <= 10^6$).
The second line contains $n$ integers $l_1$, $l_2$, $\\dots$, $l_n$ ($1 <= l_i <= i$ for each $i$).
The third line contains $n$ integers $r_1$, $r_2$, $\\dots$, $r_n$ ($i <= r_i <= n$ for each $i$).
It is guaranteed that the sum of $n$ in all test cases is no more than $3 times 10^6$.
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 to the corresponding case.
## Input
The input contains multiple test cases.For each test case, the first line contains an integer $n$ ($1 <= n <= 10^6$).The second line contains $n$ integers $l_1$, $l_2$, $\\dots$, $l_n$ ($1 <= l_i <= i$ for each $i$).The third line contains $n$ integers $r_1$, $r_2$, $\\dots$, $r_n$ ($i <= r_i <= n$ for each $i$).It is guaranteed that the sum of $n$ in all test cases is no more than $3 times 10^6$.
## 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 to the corresponding case.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $.
Let $ l = (l_1, \dots, l_n) $, $ r = (r_1, \dots, r_n) $ be sequences of integers such that $ 1 \le l_i \le i \le r_i \le n $ for all $ i \in \{1, \dots, n\} $.
Let $ \mathcal{P}_n $ be the set of all permutations of $ \{1, 2, \dots, n\} $.
For a permutation $ p = (p_1, \dots, p_n) \in \mathcal{P}_n $, define for each $ i \in \{1, \dots, n\} $:
$$
(l_i(p), r_i(p)) = \left( \min \{ L \mid \min_{j=L}^R p_j = p_i \}, \max \{ R \mid \min_{j=L}^R p_j = p_i \} \right)
$$
where the minima are taken over contiguous subarrays containing index $ i $, and $ (l_i(p), r_i(p)) $ is the unique maximal interval such that $ p_i $ is the minimum in $ p[L:R] $ if and only if $ l_i(p) \le L \le i \le R \le r_i(p) $.
**Constraints**
For each test case:
1. $ 1 \le n \le 10^6 $
2. $ 1 \le l_i \le i \le r_i \le n $ for all $ i \in \{1, \dots, n\} $
3. Total $ n $ across all test cases $ \le 3 \times 10^6 $
**Objective**
Count the number of permutations $ p \in \mathcal{P}_n $ such that for all $ i \in \{1, \dots, n\} $:
$$
l_i(p) = l_i \quad \text{and} \quad r_i(p) = r_i
$$
Output the count modulo $ 10^9 + 7 $.