There are many high-achieving students in the G department at THU, such as student R's roommate, God B. God B is tired of comparing his GPA (Grade Point Average) with other students; he only cares about how many students in the G department are "crushed" by him.

God B claims that there are $k$ students in the G department who are crushed by him.

God D, another high-achiever in the G department, thinks God B is bragging. He looked up God B's ranking in each required course in the G department. It took him 173 milliseconds to calculate how many scenarios exist where God B's statement holds true. Now he wants to test you, the clever one, to see if you can also calculate this number of scenarios.

Description

There are $n$ students and $m$ required courses in the G department. These $n$ students are numbered from $0$ to $n-1$, where God B is numbered $0$. These $m$ required courses are numbered from $0$ to $m-1$. A student can receive an integer score from $1$ to $u_i$ in required course $i$.

If student A's score in every course is less than or equal to God B's score, we say A is "crushed" by B.

According to God B's statement, there are $k$ students in the G department who are crushed by him (excluding himself), while the other $n-k-1$ students are not crushed by him.

God D looked up God B's ranking in each required course. The ranking here means: if God B's rank in a certain course is $r_i$, it means there are exactly $r_i-1$ students whose scores in this course are greater than God B's score, and there are exactly $n-r_i$ students whose scores in this course are less than or equal to God B's (excluding himself).

We need to calculate the number of scenarios for all students' scores in each required course such that they satisfy both God B's statement and the rankings found by God D. Two scenarios are considered different if and only if any student has a different score in any course.

You do not need to be as capable as God D; you only need to calculate the number of scenarios modulo $10^9 + 7$.

Input

The first line of the input contains three positive integers $n, m, k$, representing the number of students in the G department (including God B), the number of required courses, and the number of students crushed by God B, respectively.

The second line contains $m$ positive integers, representing the maximum score $u_i$ for each course.

The third line contains $m$ positive integers, representing God B's rank $r_i$ in each course. It is guaranteed that $1 \le r_i \le n$.

The data guarantees that there is at least one scenario where God B's statement holds true.

Output

The output contains a single integer, representing the number of scenarios satisfying the conditions modulo $10^9 + 7$.

Examples

Input 1

3 2 1
2 2
1 2

Output 1

10

Note

There are exactly 10 scenarios that satisfy the conditions.

Input 2

5 3 2
4 3 2
2 1 2

Output 2

54096

Subtasks