题目描述

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,\ldots,a_N$。

第三行包含 $b_1,b_2,\ldots,b_N$。

输出格式

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

2
1 2
2 2

2

3
1 3 2
2 2 2

3

5
2 5 1 3 2
2 1 5 2 2

1

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

140

提示

样例解释 1

两种合法的方法为：

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

样例解释 2

三种合法的方法为：

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

样例解释 3

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

测试点性质

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