AtCoder Regular Contest 053

D - 2 つの山札


Time limit時間制限 : 5sec / Memory limitメモリ制限 : 256MB

問題文

それぞれ 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

Submit提出する