Thời khóa biểu

Một khoa có $N$ nhóm sinh viên, và hành lang giảng đường có $M$ phòng học được đánh số từ $1$ đến $M$. Mỗi ngày mỗi nhóm có hai tiết học liên tiếp, mỗi tiết diễn ra ở một phòng nào đó. Quy ước rằng số hiệu phòng của tiết một của một nhóm không vượt quá số hiệu phòng của tiết hai của nhóm đó.

Một thời khóa biểu là một bộ gồm $2N$ số: với mỗi nhóm, xác định số hiệu phòng của tiết một và tiết hai. Cho hai dãy $X_1,X_2,\dots ,X_M$ và $Y_1,Y_2,\dots ,Y_M$. Đếm số thời khóa biểu hợp lệ thỏa mãn:

1. Trong tiết một, phòng $i$ chứa đúng $X_i$ nhóm.
2. Tại mọi tiết (cả tiết một lẫn tiết hai), phòng $i$ chứa không quá $Y_i$ nhóm.

Các nhóm được phân biệt với nhau. Hai thời khóa biểu được coi là khác nhau nếu tồn tại một nhóm mà một trong hai số hiệu phòng (tiết một hoặc tiết hai) khác nhau.

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

Dữ liệu vào

• Dòng đầu chứa một số nguyên $M$ — số phòng học.
• Dòng thứ hai chứa $M$ số nguyên $X_1,X_2,\dots ,X_M$.
• Dòng thứ ba chứa $M$ số nguyên $Y_1,Y_2,\dots ,Y_M$.

Dữ liệu ra

• In ra số thời khóa biểu hợp lệ modulo ${10}^9+7$.

Ràng buộc

• $1\le M\le 100$
• $0\le X_i\le 100$
• $0\le Y_i\le 100$
• $X_i\le Y_i$ với mọi $i$
• $1\le \sum X_i\le 1000$ (đây cũng là $N$ — số nhóm)

Ví dụ