题目描述

给定一个长度为 $n$ 的排列 $p$ 和一个长度为 $n$ 的数组 $q$ 。你可以进行如下操作任意多次（包括 $0$ 次）：选择两个下标 $i$ , $j$ ，交换 $p_i$ 和 $p_j$ 。

求有多少种操作完后的排列满足 $p$ 中的每个位置小于等于 $q$ 中的对应位置。即， $\forall i\in[1,n], p_i\leq q_i$ 。你需要输出总数对 $10^9+7$ 取模后的结果。

输入格式

第一行一个整数 $n$ 。

第二行 $n$ 个互不相同的整数，代表排列 $p$ 。

第三行 $n$ 个整数，代表数组 $q$ 。

一行一个整数，表示答案对 $10^9+7$ 取模后的结果

4
4 3 2 1
4 4 2 2

5
1 2 3 4 5
1 1 3 5 5

对于样例 $1$ ，可能的排列有 $[3,4,1,2]$ , $[4,3,1,2]$ , $[3,4,2,1]$ , $[4,3,2,1]$ 。

对于样例 $2$ ，因为只有一个 $1$ ，所以第一个和第二个位置有一个位置会无法放置，答案为 $0$ 。

对于 $40\%$ 的数据， $n\leq 10$ ；

对于 $50\%$ 的数据， $n\leq 20$ ；

对于 $60\%$ 的数据， $n\leq 10^3$ ；

对于另外 $20\%$ 的数据，数组 $q$ 中整数互不相同。

对于所有数据， $1\leq n\leq 10^5$ , $1\leq p_i,q_i\leq n$ 。