A6080 | $「HAOI2018」奇怪的背包$

时间限制2s

内存限制512MB

通过 / 提交0/0

题目描述

小 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

C++ 编辑器

输入

输出