Problem Description

Bessie has two arrays of length $N$ ($1 \le N \le 500$). The $i$-th element of the first array is $a_i$ ($1 \le a_i \le 10^6$), and the $i$-th element of the second array is $b_i$ ($1 \le b_i \le 10^6$).

Bessie wants to partition both arrays into several non-empty subarrays such that the following conditions are met:

1. Each element belongs to exactly one subarray.
2. Both arrays are partitioned into the same number of subarrays. Let the number of subarrays be $k$ (i.e., the first array is partitioned into exactly $k$ subarrays, and the second array is partitioned into exactly $k$ subarrays).
3. For all $1 \le i \le k$, the average of the $i$-th subarray from the left in the first array is less than or equal to the average of the $i$-th subarray from the left in the second array.

Calculate the number of ways she can partition the two arrays into non-empty subarrays under these constraints, modulo $10^9 + 7$. Two partitioning methods are considered different if the number of subarrays is different or if any element belongs to a different subarray.

Input Format

The first line of input contains $N$.

The second line contains $a_1, a_2, \ldots, a_N$.

The third line contains $b_1, b_2, \ldots, b_N$.

Output Format

Output the number of ways to partition the two arrays into non-empty subarrays under the constraints, modulo $10^9 + 7$.

Sample Input and Output

Sample Input #1

2
1 2
2 2

Sample Output #1

2

Sample Input #2

3
1 3 2
2 2 2

Sample Output #2

3

Sample Input #3

5
2 5 1 3 2
2 1 5 2 2

Sample Output #3

1

Sample Input #4

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

Sample Output #4

140

Notes/Hints

Sample Explanation 1

The two valid methods are:

1. Partition the first array into $[1], [2]$ and the second array into $[2], [2]$.
2. Partition the first array into $[1, 2]$ and the second array into $[2, 2]$.

Sample Explanation 2

The three valid methods are:

1. Partition the first array into $[1, 3], [2]$ and the second array into $[2, 2], [2]$.
2. Partition the first array into $[1, 3], [2]$ and the second array into $[2], [2, 2]$.
3. Partition the first array into $[1, 3, 2]$ and the second array into $[2, 2, 2]$.

Sample Explanation 3

The only valid method is to partition the first array into $[2], [5, 1, 3], [2]$ and the second array into $[2], [1, 5], [2, 2]$.

Test Case Properties

• Test cases $5-6$: $N \le 10$.
• Test cases $7-9$: $N \le 80$.
• Test cases $10-17$: $N \le 300$.
• Test cases $18-20$: $N \le 500$.

见题面 Input 部分

见题面 Output 部分