YZOJ P3098 [JLOI2016]成绩比较

时间限制：100MS      内存限制：131072KB

难度：\(6.0\)

• 题目描述

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 \leq R_i \leq n\)。

数据保证至少有 \(1\) 种情况使得B神说的话成立。\(n \leq 100, m \leq 100, U_i \leq 10^9\) 。

• 输出格式

输出仅包括一行一个整数，表示成绩情况数对 \(10^9+7\) 取模的结果。

• 样例输入

• 样例输出

• 数据规模与约定

对于 \(30\%\) 的数据，\(n, m \leq 20\)，\(U_i \leq 100\)；

对于 \(100\%\) 的数据，\(n,m \leq 100\)，\(U_i \leq 10^9\)，\(1 \leq R_i \leq n\)，\(0 \leq k < n\) …