#P647. 【HAOI2018】奇怪的背包

【HAOI2018】奇怪的背包

题目描述

小 C 非常擅长背包问题,他有一个奇怪的背包,这个背包有一个参数 P,当他向这个背包内放入若干个物品后,背包的重量是物品总体积对 P 取模后的结果。

现在小 C 有 n 种体积不同的物品,第 i 种占用体积为 Vi,每种物品都有无限个。他会进行 q 次询问,每次询问给出重量 wi,你需要回答有多少种放入物品的方案,能将一个初始为空的背包的重量变为 wi。注意,两种方案被认为是不同的,当且仅当放入物品的种类不同,而与每种物品放入的个数无关。不难发现总的方案数为 2^n。

由于答案可能很大,你只需要输出答案对 10^9+7 取模的结果。

输入格式

第一行三个整数 n,q,P

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

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

输出格式

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

样例输入

3 3 6
1 3 4
5 2 3

样例输出

5 
6
6

样例解释

对于第一个询问 5,选择 {1},{1,3},{1,4},{3,4},{1,3,4} 都是合法的方案。

数据范围与约定

对于所有数据,有 1n,q10^6,3P10^9,0<Vi,wi<P

保证 Vi 两两不同。