D - 2 つの山札
解説
/
実行時間制限: 5 sec / メモリ制限: 256 MB
問題文
それぞれ 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