题目描述

G 系共有 $N$ 位同学，$M$ 门必修课。这 $N$ 位同学的编号为 $0$ 到 $N-1$ 的整数，其中 B 神的编号为 $0$ 号。这 $M$ 门必修课编号为 $0$ 到 $M-1$ 的整数。一位同学在必修课上可以获得的分数是 $1$ 到 $U_i$ 中的一个整数。

如果在每门课上 A 获得的成绩均小于等于 B 获得的成绩，则称 A 被 B 碾压。在 B 神的说法中，G 系共有 $K$ 位同学被他碾压（不包括他自己），而其他 $N-K-1$ 位同学则没有被他碾压。D 神查到了 B 神每门必修课的排名。

这里的排名是指：如果 B 神某门课的排名为 $R$，则表示有且仅有 $R-1$ 位同学这门课的分数大于 B 神的分数，有且仅有 $N-R$ 位同学这门课的分数小于等于 B 神（不包括他自己）。

我们需要求出全系所有同学每门必修课得分的情况数，使其既能满足 B 神的说法，也能符合 D 神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。

你不需要像 D 神那么厉害，你只需要计算出情况数模 $10^9+7$ 的余数就可以了。

输入格式

第一行包含三个正整数 $N,M,K$，分别表示 G 系的同学数量（包括 B 神），必修课的数量和被 B 神碾压的同学数量。

第二行包含 $M$ 个正整数，依次表示每门课的最高分 $U_i$。

第三行包含 $M$ 个正整数，依次表示 B 神在每门课上的排名 $R_i$。

数据保证至少有 $1$ 种情况使得 B 神说的话成立。

输出格式

仅一行一个正整数，表示满足条件的情况数模 $10^9+7$ 的余数。

3 2 1
2 2
1 2

10

提示

$1\leq N\leq 100$，$1\leq M\leq 100$，$1\leq U_i\leq 10^9$，$1\leq R_i\leq N$。