18542번 - Permutant 다국어

Consider an \(n \times n\) matrix \(A\). Let us denote element in \(i\)-th row and \(j\)-th column as \(A_j^{(i)}\).

You are given a sequence \(a_1, \dots , a_n\) and a permutation \(π_1, \dots , π_n\) such that the first row is formed by sequence \(a_k\):

\[A_k^{(1)} = a_k\]

And any consequent row is formed by applying permutation \(π_k\) to the previous one:

\[A_k^{(i)} = A_{π_k}^{(i-1)}\]

Your task is to calculate \(\det {A}\): the determinant of matrix \(A\). Since it may be very large, output it modulo \(10^9 + 7\).

The first line of input contains a single integer \(n\) (\(1 \le n \le 5000\)).

The second line of input contains \(n\) integers \(a_1, \dots , a_n\) (\(1 \le a_i \le 10^9\)).

The third line of input contains \(n\) distinct integers \(π_1, \dots , π_n\) (\(1 \le π_i \le n\)).

Output a single number which is the answer to the problem.

Recall that the determinant can be defined as follows:

\[\det{A} = \sum_{\sigma \in S_n}{\text{sgn}(\sigma)} \prod_{i=1}^{n}{A_{\sigma_i}^{(i)}}\]

Here, \(S_n\) is the set of all permutations of \(\{1, \dots , n\}\), and \(\text{sgn}(\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\) .