1096: 奇怪的背包

内存限制:128 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:11 通过:5

题目描述

小 C 非常擅长背包问题,他有一个奇怪的背包,这个背包有一个参数 P ,当他向这个背包内放入若干个物品后,背包的重量是物品总体积对P  取模后的结果.
现在小 C 有 n  种体积不同的物品,第 i 种占用体积为 Vi  ,每种物品都有无限个.他会进行 q 次询问,每次询问给出重量 wi ,你需要回答有多少种放入物品的方案,能将一个初始为空的背包的重量变为 wi.注意,两种方案被认为是不同的,当且仅当放入物品的种类不同,而与每种物品放入的个数无关.不难发现总的方案数为2n  .
由于答案可能很大,你只需要输出答案对 109+7  取模的结果.


输入格式



第一行三个整数  n,q,P,含义见问题描述.

接下来一行 n  个整数表示  Vi .

接下来一行 q 个整数表示  wi.


输出格式



输出  q 行,每行一个整数表示答案.




输入样例 复制

3 3 6
1 3 4
5 2 3

输出样例 复制

5
6
6

数据范围与提示

分类标签