問題文
每个 N 一堆卡片 2 有一个。设这些为 A 山和 B 山。
从A山顶 第 i 卡包含一个整数 写入 a_i 。然而, 排列最多为(a_1,...,a_N) 为 1 从 N 。
从B山顶 i 卡包含一个整数 写入 b_i 。然而, 排列最多为(b_1,...,b_N) 为 1 从 N 。
高桥先生执行以下一系列操作。 2N-2 次、长度 创建 2N-2 序列。
- A 堆和 B 堆中的牌是 2 选择剩下 1 张以上牌的玩家。
- 移除所选牌堆的顶牌。
- 将您未选择的那堆最上面的卡片上写的数字添加到数字序列的末尾。
高桥可以创建多少个数字序列? 除以10^9+7 求余数。 它是直到
制約
- 2≦N≦1,000
- (a_1,...,a_N) 为 1 从 N 的排列。 打印除以
- (b_1,...,b_N) 为 1 从 N 的排列。 打印除以
入力
输入将以以下格式从标准输入给出。
N a_1 ... a_N b_1 ... b_N
出力
高桥可以创建多少个数字序列? 除以10^9+7 后的余数。
入力例1
2 1 2 2 1
出力例1
2
如果按顺序选择 A 山和 B 山,则顺序为 得到 (2,2) ,如果按顺序选择B山和A山,就会得到一个序列 您将得到 (1,1) 。
入力例2
3 1 2 3 2 3 1
出力例2
5
下一步 5 您可以创建数字序列。
- (1,1,1,1)
- (1,3,2,1)
- (1,3,3,3)
- (2,2,2,1)
- (2,2,3,3)
入力例3
5 3 1 4 2 5 3 2 4 1 5
出力例3
58