问题文

有两堆牌，每堆有 $N$ 张牌，分别称为山 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$ 张牌的一边。
• 移除所选边的顶部牌。
• 将未选择的边的顶部牌上的数字添加到数列的末尾。

请计算高桥君能够创建的数列有多少种，将其除以 $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