考虑一个 $n \times n$ 的矩阵 $A$。记第 $i$ 行第 $j$ 列的元素为 $A_j^{(i)}$。 给定一个序列 $a_1, \dots, a_n$ 和一个排列 $\pi_1, \dots, \pi_n$，使得第一行由序列 $a_k$ 构成： $$A_k^{(1)} = a_k$$ 后续的每一行由前一行应用排列 $\pi_k$ 得到： $$A_k^{(i)} = A_{\pi_k}^{(i-1)}$$ 你的任务是计算 $\det A$，即矩阵 $A$ 的行列式。由于结果可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5000$)。 第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$)。 第三行包含 $n$ 个不同的整数 $\pi_1, \dots, \pi_n$ ($1 \le \pi_i \le n$)。

输出格式

输出一个数字，即问题的答案。

样例

样例输入 1

4
1 1 1 1
4 2 3 1

样例输出 1

0

样例输入 2

2
2 1
2 1

样例输出 2

3

说明

回想行列式的定义如下： $$\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$ 的符号：如果 $\sigma$ 有奇数个逆序对，则为 $-1$，如果逆序对数量为偶数，则为 $+1$。逆序对是指满足 $i < j$ 但 $\sigma_i > \sigma_j$ 的下标对 $(i, j)$。