{"problem":{"name":"G. Permutant","description":{"content":"Consider an $n times n$ matrix $A$. Let us denote element in $i$-th row and $j$-th column as $A^((i))_j$. You are given a sequence $a_1, \\\\dots, a_n$ and a permutation $pi_1, \\\\dots, pi_n$ such that ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10212G"},"statements":[{"statement_type":"Markdown","content":"Consider an $n times n$ matrix $A$. Let us denote element in $i$-th row and $j$-th column as $A^((i))_j$.\n\nYou are given a sequence $a_1, \\\\dots, a_n$ and a permutation $pi_1, \\\\dots, pi_n$ such that the first row is formed by sequence $a_k$:\n\n$$A^{(1)}_k = a_k$$ \n\nAnd any consequent row is formed by applying permutation $pi_k$ to the previous one: \n\n$$A^{(i)}_k = A^{(i-1)}_{\\pi_k}$$ \n\nYour task is to calculate $det A$: the determinant of matrix $A$. Since it may be very large, output it modulo $10^9 + 7$.\n\nThe first line of input contains a single integer $n$ ($1 <= n <= 5000$).\n\nThe second line of input contains $n$ integers $a_1, \\\\dots, a_n$ ($1 <= a_i <= 10^9$).\n\nThe third line of input contains $n$ distinct integers $pi_1, \\\\dots, pi_n$ ($1 <= pi_i <= n$).\n\nOutput a single number which is the answer to the problem.\n\nRecall that the determinant can be defined as follows:\n\n$$\\det A = \\sum\\limits_{\\sigma \\in S_n} \\mathrm{sgn} (\\sigma) \\prod\\limits_{i = 1}^{n} A^{(i)}_{\\sigma_i}$$\n\nHere, $S_n$ is the set of all permutations of ${1, \\\\dots, n}$, and $upright(s g n) (sigma)$ is the sign of permutation $sigma$: $-1$ if it has an odd number of inversions and $+ 1$ if this number is even. An inversion is a pair of indices $(i, j)$ such that $i < j$ but $sigma_i > sigma_j$.\n\n## Input\n\nThe first line of input contains a single integer $n$ ($1 <= n <= 5000$).The second line of input contains $n$ integers $a_1, \\\\dots, a_n$ ($1 <= a_i <= 10^9$).The third line of input contains $n$ distinct integers $pi_1, \\\\dots, pi_n$ ($1 <= pi_i <= n$).\n\n## Output\n\nOutput a single number which is the answer to the problem.\n\n[samples]\n\n## Note\n\nRecall that the determinant can be defined as follows:$$\\det A = \\sum\\limits_{\\sigma \\in S_n} \\mathrm{sgn} (\\sigma) \\prod\\limits_{i = 1}^{n} A^{(i)}_{\\sigma_i}$$Here, $S_n$ is the set of all permutations of ${1, \\\\dots, n}$, and $upright(s g n) (sigma)$ is the sign of permutation $sigma$: $-1$ if it has an odd number of inversions and $+ 1$ if this number is even. An inversion is a pair of indices $(i, j)$ such that $i < j$ but $sigma_i > sigma_j$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ \\mathbf{a} = (a_1, \\dots, a_n) \\in \\mathbb{Z}^n $, and $ \\pi = (\\pi_1, \\dots, \\pi_n) \\in S_n $ be a permutation.  \nDefine the $ n \\times n $ matrix $ A $ such that:  \n- $ A^{(1)}_j = a_j $ for $ j = 1, \\dots, n $,  \n- $ A^{(i)}_j = A^{(i-1)}_{\\pi_j} $ for $ i = 2, \\dots, n $ and $ j = 1, \\dots, n $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 5000 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i $  \n3. $ \\pi \\in S_n $, i.e., $ \\pi $ is a permutation of $ \\{1, \\dots, n\\} $  \n\n**Objective**  \nCompute $ \\det A \\mod (10^9 + 7) $, where:  \n$$\n\\det A = \\sum_{\\sigma \\in S_n} \\mathrm{sgn}(\\sigma) \\prod_{i=1}^n A^{(i)}_{\\sigma_i}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10212G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}