{"raw_statement":[{"iden":"statement","content":"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$.\n\nGiven 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.\n\nThe answer may be exceedingly large, so you should output the answer modulo $(10^9 + 7)$ instead.\n\nThe input contains multiple test cases.\n\nFor each test case, the first line contains an integer $n$ ($1 <= n <= 10^6$).\n\nThe second line contains $n$ integers $l_1$, $l_2$, $\\\\dots$, $l_n$ ($1 <= l_i <= i$ for each $i$).\n\nThe third line contains $n$ integers $r_1$, $r_2$, $\\\\dots$, $r_n$ ($i <= r_i <= n$ for each $i$).\n\nIt is guaranteed that the sum of $n$ in all test cases is no more than $3 times 10^6$.\n\nFor 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.\n\n"},{"iden":"input","content":"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$."},{"iden":"output","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $.  \nLet $ 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\\} $.  \n\nLet $ \\mathcal{P}_n $ be the set of all permutations of $ \\{1, 2, \\dots, n\\} $.  \nFor a permutation $ p = (p_1, \\dots, p_n) \\in \\mathcal{P}_n $, define for each $ i \\in \\{1, \\dots, n\\} $:  \n$$\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)\n$$  \nwhere 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) $.\n\n**Constraints**  \nFor each test case:  \n1. $ 1 \\le n \\le 10^6 $  \n2. $ 1 \\le l_i \\le i \\le r_i \\le n $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. Total $ n $ across all test cases $ \\le 3 \\times 10^6 $\n\n**Objective**  \nCount the number of permutations $ p \\in \\mathcal{P}_n $ such that for all $ i \\in \\{1, \\dots, n\\} $:  \n$$\nl_i(p) = l_i \\quad \\text{and} \\quad r_i(p) = r_i\n$$  \nOutput the count modulo $ 10^9 + 7 $.","simple_statement":"Given n and for each position i, you're given l_i and r_i.  \nCount the number of permutations of [1, n] such that the minimum in the subarray [l_i, r_i] is exactly at position i, and no smaller subarray containing i has minimum at i.  \nAnswer modulo 10^9 + 7.","has_page_source":false}