시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 27 8 4 22.222%

## 문제

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.

## 예제 입력 1

4
1 1 1 1
4 2 3 1


## 예제 출력 1

0


## 예제 입력 2

2
2 1
2 1


## 예제 출력 2

3


## 노트

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$ .