{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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$)."},{"iden":"output","content":"Output a single number which is the answer to the problem."},{"iden":"examples","content":"Input4\n1 1 1 1\n4 2 3 1\nOutput0\nInput2\n2 1\n2 1\nOutput3\n"},{"iden":"note","content":"Recall 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$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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$$","simple_statement":"You are given an n×n matrix A.  \nThe first row is a sequence a₁, a₂, ..., aₙ.  \nEach next row is created by rearranging the previous row using a permutation π:  \nA[i][j] = A[i-1][π[j]].  \n\nCompute the determinant of A modulo 10⁹ + 7.","has_page_source":false}