問題文

それぞれ $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$ 枚以上残っている方を好きに選ぶ。
• 選んだ方の山の一番上のカードを取り除く。
• 選ばなかった方の山の一番上のカードに書かれた数を、数列の末尾に追加する。

高橋君が作ることのできる数列は何通りか、$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