Problem Description

Alpinists Takahashi and Aoki recently conquered a famous mountain range. This mountain range consists of \( N \) mountains, arranged in a straight line from west to east: mountain \( 1 \), mountain \( 2 \), \( \ldots \), mountain \( N \). Takahashi started from the west, and Aoki from the east to conquer this mountain range.

The height of mountain \( i \) is \( h_i \), but both of them forgot the values of each \( h_i \). Instead, for each \( i \) ( \( 1 \leq i \leq N \) ), they recorded the maximum height of the mountains they climbed (including mountain \( i \)) when they reached the summit of mountain \( i \). Takahashi's recorded values are \( T_i \), and Aoki's recorded values are \( A_i \).

It is known that the height of each mountain \( h_i \) is a positive integer. Determine the number of possible sequences of mountain heights, modulo \( 10^9+7 \).

Note that there might be no possible sequence of mountain heights due to incorrect records. In this case, output \( 0 \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( T_1 \) \( T_2 \) \( \ldots \) \( T_N \) \( A_1 \) \( A_2 \) \( \ldots \) \( A_N \)

Output Format

Output the number of possible sequences of mountain heights, modulo \( 10^9+7 \).

Sample Input and Output

Sample Input #1

5
1 3 3 3 3
3 3 2 2 2

Sample Output #1

4

Sample Input #2

5
1 1 1 2 2
3 2 1 1 1

Sample Output #2

0

Sample Input #3

10
1 3776 3776 8848 8848 8848 8848 8848 8848 8848
8848 8848 8848 8848 8848 8848 8848 8848 3776 5

Sample Output #3

884111967

Sample Input #4

1
17
17

Sample Output #4

1

Notes/Hints

Constraints

• \( 1 \leq N \leq 10^5 \)
• \( 1 \leq T_i \leq 10^9 \)
• \( 1 \leq A_i \leq 10^9 \)
• \( T_i \leq T_{i+1} \) ( \( 1 \leq i \leq N-1 \) )
• \( A_i \geq A_{i+1} \) ( \( 1 \leq i \leq N-1 \) )

Sample Explanation 1

The possible sequences of mountain heights are:
- \( 1, 3, 2, 2, 2 \)
- \( 1, 3, 2, 1, 2 \)
- \( 1, 3, 1, 2, 2 \)
- \( 1, 3, 1, 1, 2 \)

There are \( 4 \) possible sequences.

Sample Explanation 2

According to Takahashi, the maximum height of the mountains after climbing all is \( 2 \), but according to Aoki, it is \( 3 \). The records are contradictory.

Sample Explanation 3

Remember to find the result modulo \( 10^9+7 \).

Sample Explanation 4

There is also a mountain range with only one mountain.

见题面 Input 部分

见题面 Output 部分