样例下载

题目描述

Farmer John 和他的死对头 Farmer Nhoj 各自组建了一只奶牛队伍进行对决。

两只队伍均含有 N 头奶牛，从左向右分别编号为 1 ~ N。每头奶牛有一个战斗力。Nhoj 的队伍中编号为 i 的奶牛的战斗力为 Ai；John 的队伍中编号为 i 的奶牛的战斗力为 Bi。

现在两只队伍要展开对决。由于场地有限，每个 Farmer 要把自己的队伍分成若干个小队，以小队为单位进行 PK。每个小队要至少包含一头奶牛，同一个小队中的奶牛在原队伍中必须是连续的。并且两只队伍划分成的小队数量是相同的，每个小队也有编号，每只队伍被划分出来的小队从左到右依次编号为 1, 2, 3, ……。

小队划分完后，便开始展开对决，John 和 Nhoj 的队伍中划分出来的编号相同的两个小队将进行同场 PK。

John 希望自己的小队中的奶牛战斗力的平均值不能低于与其 PK 的对手小队的奶牛战斗力的平均值。他想知道有多少种划分方式可以实现他的希望。

你能帮助他吗？答案可能很大，你需要输出答案 mod $(10^9+7)$。

注：两种划分方式不同，当且仅当满足下列条件之一：

（1）划分出来的小队数量不同；

（2）划分出来的小队数量相同，但至少有一头奶牛被分到了编号不同的小队中。

输入格式

第一行：一个整数 $N$。

第二行：$N$ 个整数 $A_i$。

第三行：$N$ 个整数 $B_i$。

输出格式

一个整数，表示答案 mod $(10^9+7)$。

样例1输入

2
1 2
2 3

样例1输出

2

样例1解释

两种划分方式：

（1）两支队伍均划分成 1 个小队，即不用划分

（2）两支队伍均划分成 2 个小队

A：1 | 2

B：2 | 3

样例2输入

3
1 3 3
2 2 3

样例2输出

3

样例2解释

三种划分方式：

（1）两支队伍均划分成 1 个小队，即不用划分

（2）两支队伍均划分成 2 个小队

A：1 3 | 3

B：2 2 | 3

（3）两支队伍均划分成 2 个小队

A：1 3 | 3

B：2 | 2 3

数据范围

100% 的数据：$1 ≤ N ≤ 500$, $1 ≤ A_i ≤ 10^6$, $1 ≤ B_i ≤ 10^6$. 其中

• 10 %的数据：$N ≤ 10$。
• 20 %的数据：$N ≤ 100$。
• 30 %的数据：$N ≤ 300$。
• 40 %的数据：$N ≤ 500$。