Bạn được cho hai mảng có độ dài ~n~ .

• Phần tử thứ ~i~ của mảng thứ nhất là ~a_i~ .
• Phần tử thứ ~i~ của mảng thứ hai là ~b_i~ .

Một cách chia cả hai mảng thành các mảng con không rỗng được gọi là tốt nếu thỏa mãn các điều kiện sau:

• Mỗi phần tử thuộc đúng một mảng con duy nhất.
• Số lượng mảng con của cả hai mảng bằng nhau, tức là nếu mảng thứ nhất được chia thành đúng ~k~ mảng con, thì mảng thứ hai cũng phải được chia thành đúng ~k~ mảng con.
• Với mọi ~1 \leq i \leq k~, trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ nhất phải nhỏ hơn hoặc bằng trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ hai.

Yêu cầu: Tính số cách để chia cả hai mảng thành các mảng con không rỗng thỏa mãn các điều kiện trên. Kết quả phải được chia dư với ~10^9 + 7~. Hai cách được xem là khác nhau nếu số lượng mảng con khác nhau hoặc nếu một phần tử thuộc về mảng con khác nhau.

Dữ liệu vào từ tệp văn bản: TRUNGBINHCONG.INP

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 500)~.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \leq a_i \leq 10^6)~.
• DDòng cuối cùng chứa ~N~ số nguyên ~b_1, b_2, \dots, b_n~ ~(1 \leq b_i \leq 10^6)~.

Kết quả ghi ra tệp văn bản: TRUNGBINHCONG.OUT

• In ra số cách chia mảng thỏa mãn các điều kiện, chia dư với ~10^9 + 7~.

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~n \le 10~
• Subtask ~2~ (~30\%~ số điểm): ~n \le 80~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 300~
• Subtask ~4~ (~20\%~ số điểm): Không giới hạn gì thêm.

Example

Sample Input 1

3
1 3 2
2 2 2

Sample Output 1

3

Note

Ba cách hợp lệ là:

• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2, 2], [2]~.
• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2], [2, 2]~.
• Chia mảng thứ nhất thành ~[1, 3, 2]~ và mảng thứ hai thành ~[2, 2, 2]~.