[HAOI2018] 奇怪的背包
题目描述
小 C 非常擅长背包问题,他有一个奇怪的背包,这个背包有一个参数 $P$ ,当他向这个背包内放入若干个物品后,背包的重量是物品总体积对 $P$ 取模后的结果。
现在小 C 有 $n$ 种体积不同的物品,第 $i$ 种占用体积为 $V_i$ ,每种物品都有无限个。他会进行 $q$ 次询问,每次询问给出重量 $w_i$ ,你需要回答有多少种放入物品的方案,能将一个初始为空的背包的重量变为 $w_i$。注意,两种方案被认为是不同的,当且仅当放入物品的种类不同,而与每种物品放入的个数无关.不难发现总的方案数为 $2^n$。
由于答案可能很大,你只需要输出答案对 $10^9 + 7$ 取模的结果。
输入输出格式
输入格式
第一行三个整数 $n, q, P$,含义见问题描述。
接下来一行 $n$ 个整数表示 $V_i$。
接下来一行 $q$ 个整数表示 $w_i$。
输出格式
输出 $q$ 行,每行一个整数表示答案。
输入输出样例
输入样例 #1
3 3 6
1 3 4
5 2 3
输出样例 #1
5
6
6
说明
![](https://cdn.luogu.com.cn/upload/pic/18144.png)
HAOI2018 round1 T1