Problem1035--#2026. 「JLOI / SHOI2016」成绩比较

1035: #2026. 「JLOI / SHOI2016」成绩比较

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

THU 的 G 系中有许许多多的大牛,比如小 R 的室友 B 神。B 神已经厌倦了与其他的同学比较 GPA(Grade Point Average,平均学分绩),他只在意 G 系中共有多少同学被他“碾压”。

B 神声称,在 G 系共有 kkk 位同学被他碾压。同是 G 系大牛的 D 神则认为 B 神在吹牛,他查到了 B 神每门必修课在 G 系的排名。他用了 173 毫秒的时间就计算出了有多少种情况使得 B 神所说的话成立。现在他想考考聪明的你,看你是否也能求出这个情况数。

G 系共有 nnn 位同学,mmm 门必修课。这 nnn 位同学的编号为 000n−1n - 1n1 的整数,其中 B 神的编号为 000 号。这 mmm 门必修课编号为 000m−1m - 1m1 的整数。如果在每门课上 A 获得的成绩均小于等于 B 获得的成绩,则称 A 被 B 碾压。在 B 神的说法中,G 系共有 kkk 位同学被碾压(不包括他自己),而其他 n−k−1n - k - 1nk1 名同学则没有被他碾压。

D 神查到了 B 神每门必修课的排名。这里的排名是指,如果 B 神某门课的排名为 rrr,则表示有且仅有 r−1r - 1r1 位同学这门课的分数大于 B 神的分数,有且仅有 n−rn - rnr 位同学这门课的分数小于等于 B 神(不包括他自己)。

我们需要求出全系所有同学每门必修课得分的情况数,使其既能满足 B 神的说法,也能符合 D 神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。你不需要像 D 神那么厉害,你只需要计算出情况数模 109+710^9 + 7109+7 的余数就可以了。

输入格式

第一行包含三个正整数 n,m,kn, m, kn,m,k,分别表示 G 系的同学数量(包括 B 神)、必修课的数量和被 B 神碾压的同学数量。
第二行包含 mmm 个正整数,依次表示每门课的最高分 uiu_iui
第三行包含 mmm 个正整数,依次表示 B 神在每门课上的排名 rir_iri。保证 1≤ri≤n1 \leq r_i \leq n1rin

数据保证至少有 111 种情况使得 B 神的描述成立。

输出格式

输出一行一个正整数,表示满足条件的情况数模 109+710^9 + 7109+7 的余数。

样例

样例输入 1

3 2 1
2 2
1 2

样例输出 1

10

样例说明 1

有且仅有以下 101010 种符合条件的情况:

#  B 神・课程 0  B 神・课程 1 同学 A・课程 0 同学 A・课程 1 同学 B・课程 0 同学 B・课程 1
1 1 1 1 1 1 2
2 1 1 1 2 1 1
3 2 1 1 1 1 2
4 2 1 1 1 2 2
5 2 1 1 2 1 1
6 2 1 1 2 2 1
7 2 1 2 1 1 2
8 2 1 2 1 2 2
9 2 1 2 2 1 1
10 2 1 2 2 2 1

样例输入 2

5 3 2
4 3 2
2 1 2

样例输出 2

54096

数据范围与提示

Case # nnn mmm uiu_iui
1 ≤3\leq 33 ≤3\leq 33 ≤4\leq 44
2 ≤3\leq 33 ≤10\leq 1010 ≤100\leq 100100
3 ≤3\leq 33 ≤100\leq 100100 ≤109\leq 10^9109
4, 5 ≤5\leq 55 ≤100\leq 100100 ≤109\leq 10^9109
6, 7 ≤50\leq 5050 ≤50\leq 5050 ≤50\leq 5050
8 ~ 10 ≤100\leq 100100 ≤100\leq 100100 ≤109\leq 10^9109

Source/Category