Description

The G Department has $N$ students and $M$ required courses. The students are numbered by integers from $0$ to $N-1$, and B Shen's number is $0$. The $M$ required courses are numbered from $0$ to $M-1$. In each required course, a student can earn an integer score from $1$ to $U_i$ inclusive.

If in every course A's score is less than or equal to B's score, then A is said to be dominated by B. According to B Shen, there are $K$ students whom he dominates (excluding himself), and the other $N-K-1$ students are not dominated by him. D Shen has found B Shen's rank in each required course.

Here, rank means: if B Shen's rank in some course is $R$, then exactly $R-1$ students have a score strictly greater than B Shen's score in that course, and exactly $N-R$ students have a score less than or equal to B Shen's score in that course (excluding himself).

We need to count the number of possible score assignments for all students in all required courses that satisfy both B Shen's statement and the ranks found by D Shen. Two assignments are different if and only if there exists at least one student and one course where the assigned score differs.

You do not need to be as powerful as D Shen; just compute the answer modulo $10^9+7$.

Input Format

• The first line contains three positive integers $N, M, K$, denoting the number of students in the G Department (including B Shen), the number of required courses, and the number of students dominated by B Shen.
• The second line contains $M$ positive integers, the maximum score $U_i$ of each course in order.
• The third line contains $M$ positive integers, B Shen's rank $R_i$ in each course in order.
• It is guaranteed that there is at least one assignment that makes B Shen's statement hold.

Output Format

Output a single integer on one line, the number of valid assignments modulo $10^9+7$.

3 2 1
2 2
1 2

10

Hint

Constraints: $1 \leq N \leq 100$, $1 \leq M \leq 100$, $1 \leq U_i \leq 10^9$, $1 \leq R_i \leq N$.

Translated by ChatGPT 5