問題文

それぞれ 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 までの順列である。

入力例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