← 返回题目列表

AtCoder · arc053_d

D. 两副牌

中文机器翻译题面 查看原题

問題文

每个 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