505018 - 成绩比较

【题目描述】成绩比较(grade)

G系共有n位同学,M门必修课。这N位同学的编号为0到N-1的整数,其中学神的编号为0号。这M门必修课编号为0到M-1的整数。一位同学在必修课上可以获得的分数是1到Ui中的一个整数。如果在每门课上A获得的成绩均小于等于B获得的成绩,则称A被B碾压。在学神的说法中,G系共有K位同学被他碾压(不包括他自己),而其他N-K-1位同学则没有被他碾压。 现查到了学神每门必修课的排名。这里的排名是指:如果学神某门课的排名为R,则表示有且仅有R-1位同学这门课的分数大于学神的分数,有且仅有N-R位同学这门课的分数小于等于学神(不包括他自己)。我们需要求出全系所有同学每门必修课得分的情况数,使其既能满足学神的说法,也能符合之前查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。 试计算出情况数模109+7的余数。

输入

第一行包含三个正整数N,M,K(N≤100,M≤100),分别表示G系的同学数量(包括学神),必修课的数量和被学神碾压的同学数量。 第二行包含M个正整数,依次表示每门课的最高分Ui(Ui≤10^9)。第三行包含M个正整数,依次表示学神在每门课上的排名Ri。保证1≤Ri≤N。数据保证至少有1种情况使得学神说的话成立。

输出

仅一行一个正整数,表示满足条件的情况数模109+7的余数。

样例

输入

3 2 1
2 2
1 2

输出

10
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题