{"problem":{"name":"L. Limited Permutation","description":{"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":131072},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10225L"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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$.\n\n## Output\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[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10225L","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}