Bessie は長さ $N$（$1\le N\le500$）の配列二つを持ち、最初の $i$ 番目は $a_i$（$1\le a_i\le10^6$）、二番目は $b_i$（$1\le b_i\le10^6$）。

両方を空でない部分配列に分けたいです。条件：

1. 各要素はちょうど一つに属する。
2. 両配列を同じ数 $k$ に分ける。
3. 各 $1\le i\le k$ で、左から $i$ 番目の第一配列の平均が第二配列の平均以下。

条件を満たす分け方を $10^9+7$ を法として数えます。個数が異なるか、要素の属する部分配列が異なれば別の分け方です。

入力

最初の行 $N$。

次の行 $a_1,a_2,\ldots,a_N$。

次の行 $b_1,b_2,\ldots,b_N$。

出力

条件を満たす非空部分配列への分け方を $10^9+7$ を法として。

入出力例

入力 1

2
1 2
2 2

出力 1

2

注記

二つの有効な分け方、第一配列、第二配列の順：

1. $[1],[2]$ / $[2],[2]$.
2. $[1,2]$ / $[2,2]$.

入力 2

3
1 3 2
2 2 2

出力 2

3

注記

三つの有効な分け方、第一配列、第二配列の順：

1. $[1,3],[2]$ / $[2,2],[2]$.
2. $[1,3],[2]$ / $[2],[2,2]$.
3. $[1,3,2]$ / $[2,2,2]$.

入力 3

5
2 5 1 3 2
2 1 5 2 2

出力 3

1

注記

唯一の分け方、第一配列、第二配列の順： $[2],[5,1,3],[2]$ / $[2],[1,5],[2,2]$.

入力 4

7
3 5 2 3 4 4 1
5 3 5 3 3 4 1

出力 4

140

小課題

• 入力 5–6：$N\le10$。
• 入力 7–9：$N\le80$。
• 入力 10–17：$N\le300$。
• 入力 18–20：$N\le500$。

問題作成：Alex Liang