시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB150321513.514%

## 문제

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