Crushing Rankings

There are \(N\) students and \(M\) mandatory courses. The students are numbered from \(0\) to \(N-1\), and the courses are numbered from \(0\) to \(M-1\). In each course \(i\), a student can score any integer between \(1\) and \(U_i\). Student \(0\) (called B) has a special role.

For each course \(i\), D recorded that B's rank is \(R_i\). The ranking is defined such that exactly \(R_i-1\) other students have a score greater than B's score in that course, and exactly \(N-R_i\) other students have a score \(\leq\) B's score.

We say that a student \(A\) is crushed by B if in every course \(i\), the score of \(A\) is \(\leq\) the score of B. According to B, exactly \(K\) students (excluding himself) are crushed by him; the remaining \(N-K-1\) students are not crushed.

Your task is to count the number of ways to assign scores to all students in every course so that both the ranking conditions and B's claim are satisfied. Two assignments are considered different if there exists at least one student and at least one course where the score differs. Since the answer might be huge, output it modulo \(10^9+7\).

Note about the score assignments:

• B's score in course \(i\) is some \(b_i\) where \(1 \le b_i \le U_i\).
• In course \(i\), exactly \(R_i-1\) other students must have scores \(> b_i\), and exactly \(N-R_i\) students must have scores \(\le b_i\).
• If we denote by X the set of students crushed by B (with \(|X|=K\) and none of these students scores more than B in any course) and by Y the rest of the students (\(|Y|=N-1-K\)), then for each course \(i\), the following holds:

• All students in X have a score in \([1,b_i]\) in course \(i\).
• Among students in Y, exactly \((N-R_i)-K\) students have scores in \([1,b_i]\) and the remaining \(R_i-1\) students have scores in \(\{b_i+1,\dots,U_i\}\).

For a fixed course \(i\) and a fixed value of B's score \(b_i\), the number of ways to assign scores in that course is:

[ \text{ways}_i(b_i) = b_i^{N-R_i} \times (U_i-b_i)^{R_i-1} ]

However, to ensure \((U_i-b_i)^{R_i-1}\) is defined with a positive base when \(R_i>1\), we require that if \(R_i>1\), then \(b_i\) can only take values in \([1, U_i-1]\) (when \(R_i=1\), \(b_i\) may be as high as \(U_i\)).

Thus, the total number of valid assignments is:

[ \binom{N-1}{K} \times \prod_{i=0}^{M-1}\left(\sum_{b_i=1}^{L_i} b_i^{N-R_i} (U_i-b_i)^{R_i-1}\right) \quad \text{mod } 10^9+7, ]

where \(L_i = U_i\) if \(R_i=1\) and \(L_i = U_i-1\) if \(R_i>1\).

If for any course \(i\) the condition \(K \leq N-R_i\) does not hold, then no valid assignment exists and the answer is 0.

inputFormat

The first line contains three integers \(N\), \(M\), and \(K\) (number of students, number of courses, and the number of students crushed by B, respectively).

The second line contains \(M\) integers \(U_0, U_1, \ldots, U_{M-1}\), where \(U_i\) is the maximum score in course \(i\).

The third line contains \(M\) integers \(R_0, R_1, \ldots, R_{M-1}\), where \(R_i\) is the rank of B in course \(i\) (as recorded by D). Recall that if B's rank in course \(i\) is \(R_i\), then exactly \(R_i-1\) students scored strictly more than B and exactly \(N-R_i\) students scored less than or equal to B (excluding B himself).

outputFormat

Output a single integer: the number of ways to assign scores to all students in all courses satisfying the conditions, modulo \(10^9+7\).

sample

3 2 1
5 5
1 2

2200