405825: GYM102129 G Permutant

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 the first row is formed by sequence $$$a_k$$$:

$$$$$$A^{(1)}_k = a_k$$$$$$

And any consequent row is formed by applying permutation $$$\pi_k$$$ to the previous one:

$$$$$$A^{(i)}_k = A^{(i-1)}_{\pi_k}$$$$$$

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 \leq n \leq 5000$$$).

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

The third line of input contains $$$n$$$ distinct integers $$$\pi_1, \dots, \pi_n$$$ ($$$1 \leq \pi_i \leq n$$$).

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

4
1 1 1 1
4 2 3 1

0

2
2 1
2 1

3

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 $$$\mathrm{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$$$.