Bessie 有两个长 $N$（$1\le N\le500$）的数组，第一数组第 $i$ 个是 $a_i$（$1\le a_i\le10^6$），第二数组第 $i$ 个是 $b_i$（$1\le b_i\le10^6$）。

她希望将两者划分成非空子数组，满足：

1. 每个元素恰好属于一个子数组。
2. 两数组都分成相同数量 $k$ 个子数组。
3. 对每个 $1\le i\le k$，从左数第一数组第 $i$ 段的平均值小于等于第二数组第 $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