Lần này, nàng bò Bessie của chúng ta có hai dãy số độ dài \(N\) \((1 \leq N \leq 500)\) là \(a\) và \(b\) \((1 \leq a_i, b_i \leq 10^6)\).

Bessie muốn chia cả hai dãy này thành các dãy con không rỗng sao cho:

• Mỗi phần tử thuộc vào đúng \(1\) dãy con.
• Hai dãy đều có cùng số lượng dãy con. Gọi số lượng dãy con này là \(k\), các dãy con được đánh số từ \(1\) đến \(k\) từ trái sang phải.
• Với mỗi dãy con \(1 \leq i \leq k\), trung bình cộng của dãy con \(i\) trên dãy \(a\) không lớn hơn trung bình cộng của dãy con \(i\) trên dãy \(b\).

Hãy đếm số cách mà Bessie có thể chia cả hai dãy thành các dãy con không rỗng thoả mãn điều kiện trên, lấy phần dư khi chia cho \(10^9 + 7\). Hai cách chia được gọi là khác nhau nếu số lượng dãy con khác nhau hoặc có một số phần tử thuộc dãy con \(i\) nào đó trong một cách chia và không thuộc dãy con \(i\) trong cách chia còn lại.

Input

• Dòng đầu tiên chứa số \(N\).
• Dòng thứ hai gồm \(N\) số \(a_1, a_2, ..., a_n\).
• Dòng thứ ba gồm \(N\) số \(b_1, b_2, ..., b_n\).

Output

• Số cách chia dãy con lấy phần dư khi chia cho \(10^9 + 7\).

Scoring

• Subtask \(1\): \(N \leq 10\)
• Subtask \(2\): \(N \leq 80\)
• Subtask \(3\): \(N \leq 300\)
• Subtask \(4\): \(N \leq 500\)

Example

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