I - マージ Editorial /

Time Limit: 4 sec / Memory Limit: 512 MB

Problem Statement

すぬけ君は、配列 P と Q をマージして配列 R を作ることにした。

  • 最初に、R は空である。
  • P または Q が空でない間、P または Q のうち空でない配列 (両方空でない場合は好きなほう) を選び、その配列の左端の要素を取り出し、R の右端にくっつける。
P, Q が与えられたとき、R としてできる配列が何通り考えられるか、\rm{mod}\ 1,000,000,007 で求めよ。 ただし、P, Q はそれぞれ 1 から N の順列になっている。

Constraints

  • 1 \leq N \leq 2000
  • P, Q は 1 から N の順列である。

Input Format

入力は以下の形式で標準入力から与えられる。 
N
P_1 ... P_N
Q_1 ... Q_N

Output Format

答えを一行に出力せよ。

Sample Input 1

4
3 1 2 4
3 1 2 4

Sample Output 1

14

Sample Input 2

10
5 7 3 1 6 4 2 10 9 8
2 8 9 1 5 6 10 4 3 7

Sample Output 2

127224