You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

三只小猪和狼的故事，小朋友们都听说过。

今天，小明代入了狼的角色。

小猪家最早只有$0$只小猪，一共有$n$年，每一年过年的时候，小猪家新出生$t$头小猪，出生了的小猪是不会死掉的，也就是第$i$年后，小猪家有$i\times t$头小猪。

小明作为狼，想一次性抓走$x$头小猪。因此他只会在某一年过年后，且小猪家有大于等于$x$头小猪的时候来抓小猪去吃。

比如一共会有$2$年，小猪家每年出生$3$头小猪（我们把第一年出生的三头编号成$1,2,3$，第二年出生的编号成$4,5,6$），小明想抓走$1$头猪去吃。

那么：他可以选择在第一年后，抓走$1,2,3$中的一头，或者是在第二年后，抓走$1,2,3,4,5,6$中的某一头。

我们称，两种抓走方案不同，当且仅当小明到来的年份不同，或者是抓走的猪的集合不同。

现在，已知小明只会来抓一次小猪，请帮助小明算一算，他有多少种方案。

输入格式

第一行输入$n,t,q$，分别表示一共几年，每年出生几头小猪，询问个数。

接下来一行$q$个数字，每个数字$x$，表示一次询问。

输出格式

对于每次询问，输出一个数字代表答案$\mod 1e9+7$。

2 3 3
1 2 6

9
18
1

样例解释 #1

对于$x=1$，可以选择第一年到来抓走三头中的任意一头，或者第二年到来抓走六头中的任意一头。

对于$x=2$，可以选择第一年来抓走三头中的两头，$3$种方案，或者第二年到来抓走六头中的任意两头。

对于$x=6$，唯一选择就是第二年来一锅端。

100 5 5
100 200 300 400 500

607952306
127400324
368336132
182468485
1

10000 10 5
12347 23478 93871 12367 1823

126940338
390208854
514580099
61236432
993596058

数据范围

对于5%的数据：$n\leq 1000,t=4$。

对于20%的数据：$n\leq 10^5,t\leq 10,q\leq 100$。

对于另30%的数据：$n\leq 10^6,t=3,q\leq 10^5$。

对于另30%的数据：$n\leq 10^5,t=10,q\leq 10^5$。

对于100%的数据：$n\leq 10^6,3\leq t\leq 10,q\leq 10^5,1\leq x\leq nt$。