Problem 3. Smaller Averages

USACO 2024 US Open Contest, Gold

Bessie 有两个长度为 $N$ 的数组（$1 \le N \le 500$）。第一个数组的第 $i$ 个元素为 $a_i$（$1 \le a_i \le 10^6$），第二个数组的第 $i$ 个元素为 $b_i$（$1 \le b_i \le 10^6$）。

Bessie 希望将两个数组均划分为若干

非空

子数组，使得以下条件成立。

1. 每个元素恰属于 1 个子数组。
2. 两个数组划分为相同数量的子数组。令第一个和第二个数组被划分为的子数组数量为 $k$（即，第一个数组被划分为恰好 $k$ 个子数组，第二个数组被划分为恰好 $k$ 个子数组）。
3. 对于所有 $1 \le i \le k$，第一个数组左数第 $i$ 个子数组的平均值小于或等于第二个数组左数第 $i$ 个子数组的平均值。

计算她有多少种方式在满足限制的情况下将两个数组划分为非空子数组，对 $10^9+7$ 取模。两种划分方式被认为是不同的，如果子数组的数量不同或是某个元素属于不同的子数组。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$。

第二行包含 $a_1,a_2,...,a_N$。

第三行包含 $b_1,b_2,...,b_N$。

输出格式（输出至终端 / 标准输出）：

输出在满足限制的情况下将两个数组划分为非空子数组的方法数模 $10^9+7$ 的余数。

输入样例：

2
1 2
2 2

输出样例：

2

两种合法的方法为：

1. 将第一个数组划分为 $[1],[2]$，第二个数组划分为 $[2],[2]$。
2. 将第一个数组划分为 $[1,2]$，第二个数组划分为 $[2,2]$。

输入样例：

3
1 3 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]$。

输入样例：

5
2 5 1 3 2
2 1 5 2 2

输出样例：

1

唯一合法的方法是将第一个数组划分为 $[2],[5,1,3],[2]$，第二个数组划分为 $[2],[1,5],[2,2]$。

输入样例：

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

输出样例：

140

测试点性质： 测试点 5-6：$N \le 10$。测试点 7-9：$N \le 80$。测试点 10-17：$N \le 300$。测试点 18-20：$N \le 500$。

供题：Alex Liang