问题1200--送分题

1200: 送分题

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

提交

题目描述

小明在参加一场考试。

这场考试有n道单选题,每题有p个选项,每题1分。

全班有m人(包括自己),因为考试太难,大家一道题都不会做,答案都是乱答的,每题答对率都是1/p。

小明通过某种不可描述的途径获取了本场考试的答案,但他不敢ak,因为这太显眼。但他又不想排名太落后,所以他现在想知道,假如自己答对k道题,自己在班上的排名期望是多少?

排名规则为:当分数不同时,分数高的排名靠前。当分数相同时,小明排名靠前。

数学期望参考链接:https://en.wikipedia.org/wiki/Expected_value


输入

第一行四个整数n,m,p,q

n是本场考试单选题数量(1<=n<=1e5)

m是全班人数(1<=m<=1e5)

p是单选题选项个数(p<=10)

q是询问数(q<=1e5)

下面q行,每行一个整数k(0<=k<=n),表示小明想答对的题目个数。

输出

对于每个询问,输出一个数,表示小明在本场考试中在全班的排名期望。由于答案可能为分数,答案对1e9+7取模。

样例输入 Copy

3 3 4 4
0
1
2
3

样例输出 Copy

406250005
812500007
281250003
1

来源/分类

KrKing