Trung Bình Nhỏ Hơn

Bessie quản lý hai mảng $a$ và $b$, mỗi mảng có $N$ phần tử ($1\le N\le 500$, $1\le a_i,b_i\le {10}^6$).

Hãy đếm số cách chia cả hai mảng thành $k$ mảng con liên tiếp không rỗng ($k$ bất kỳ, giống nhau cho cả hai) sao cho: với mọi $1\le i\le k$, trung bình cộng của mảng con thứ $i$ của mảng $a$ nhỏ hơn hoặc bằng trung bình cộng của mảng con thứ $i$ của mảng $b$.

In kết quả modulo ${10}^9+7$.

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• Dòng 2: $N$ số nguyên $a_1,a_2,\dots ,a_N$
• Dòng 3: $N$ số nguyên $b_1,b_2,\dots ,b_N$

Dữ liệu ra

Một số nguyên -- số cách chia hợp lệ, modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le 500$
• $1\le a_i,b_i\le {10}^6$
• Test 5-6: $N\le 10$
• Test 7-9: $N\le 80$
• Test 10-17: $N\le 300$

Ví dụ