Permutant

$n \times n$ 행렬 $A$를 생각한다. $A_j^{(i)}$는 $i$행 $j$열의 원소를 나타낸다. 수열 $a_1, \dots, a_n$과 순열 $\pi_1, \dots, \pi_n$이 주어진다. 첫 번째 행은 수열 $a$로 채운다. $A_k^{(1)} = a_k$ 그 다음 행은 바로 윗행에 순열 $\pi_k$를 적용해서 만든다. $A_k^{(i)} = A_{\pi_k}^{(i-1)}$ 행렬 $A$의 행렬식 $\det A$를 구한다. 값이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 줄에 정수 $n$ ($1 \le n \le 5000$)이 주어진다. 둘째 줄에 정수 $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$)이 주어진다. 셋째 줄에 서로 다른 정수 $\pi_1, \dots, \pi_n$ ($1 \le \pi_i \le n$)이 주어진다.

답 하나를 출력한다.

행렬식은 다음과 같이 정의된다. $\det{A} = \sum_{\sigma \in S_n}{\text{sgn}(\sigma)} \prod_{i=1}^{n}{A_{\sigma_i}^{(i)}}$ 여기서 $S_n$은 $\{1, \dots, n\}$의 모든 순열의 집합이고, $\text{sgn}(\sigma)$는 $\sigma$의 부호이다. 역순서쌍의 개수가 홀수이면 $-1$, 짝수이면 $+1$이다. 역순서쌍은 $i < j$이면서 $\sigma_i > \sigma_j$인 인덱스 쌍 $(i, j)$이다.