1. 题意理解

我们有：

• $n$ 种物品，体积分别为 $V_1, V_2, \dots, V_n$，每种无限个。
• 一个背包，放入物品后总重量 = 总体积对 $P$ 取模。
• 两种方案不同 ⇔ 选择的物品集合不同（与个数无关）。
• 对于每个询问 $w_i$，求有多少种选择物品的子集，使得这些物品的总体积模 $P$ 等于 $w_i$。
• 答案对 $10^9+7$ 取模。

2. 关键点

1. 无限个但只关心选不选
   因为无限个，所以如果选了某种物品，我们可以取任意正整数个，但这里只关心“是否选这种物品”，因为不同个数模 $P$ 的效果可以通过调整数量实现。

2. 模意义下的组合
   我们选一个物品集合 $S \subseteq \{1,\dots,n\}$，那么能生成的“重量”是： [ \left{ \sum_{i \in S} k_i V_i \bmod P \ \middle|\ k_i \ge 1 \right} ] 但 $k_i \ge 1$ 表示至少一个，其实可以取任意正整数，所以能生成的重量是 $\langle V_i : i \in S \rangle$ 在模 $P$ 下的加法子群中的某些元素。

3. 群论观点
   设 $G = \mathbb{Z}_P$（模 $P$ 加法群）。
   每种物品 $V_i$ 是群里的一个元素。
   我们选一个子集 $S$，它生成的子群是 $\langle S \rangle$，这个子群的大小（阶）是 $P / \gcd(P, \gcd_{i\in S} V_i)$ 吗？不完全是，应该是 $P / \gcd(P, V_{i_1}, V_{i_2}, \dots)$。

   更准确：
   设 $d_S = \gcd(P, V_i : i \in S)$。
   那么 $S$ 能生成的重量集合是 $\{0, d_S, 2d_S, \dots, (P/d_S - 1)d_S\}$，即子群大小为 $P/d_S$。

3. 问题转化

对于询问 $w$，我们要求： [ \sum_{S \subseteq [n]} [w \in \langle S \rangle] ] 其中 $\langle S \rangle$ 是 $S$ 中元素在 $\mathbb{Z}_P$ 中生成的子群。

设 $d_S = \gcd(P, \{V_i\}_{i\in S})$，那么 $\langle S \rangle = \{0, d_S, 2d_S, \dots\}$。

条件 $w \in \langle S \rangle$ ⇔ $d_S \mid w$（在整数意义上）。

所以： [ \text{Answer}(w) = \sum_{d \mid w} f(d) ] 其中 $f(d)$ = 满足 $\gcd(P, \{V_i\}_{i\in S}) = d$ 的子集 $S$ 的数量。

4. 计算 $f(d)$

设 $g(d)$ = 满足 $d \mid \gcd(P, \{V_i\}_{i\in S})$ 的子集数，即所有选的 $V_i$ 都被 $d$ 整除（模 $P$ 意义下，即 $d \mid V_i$ 在整数意义上）。

那么： [ g(d) = 2^{#{i : d \mid V_i}} ] 因为只能选那些 $V_i$ 是 $d$ 的倍数的物品。

由莫比乌斯反演： [ f(d) = \sum_{e \mid \frac{P}{d}} \mu(e) , g(de) ] 因为 $d \mid P$ 才可能有非零 $f(d)$。

5. 简化

我们只需对每个 $d \mid P$ 计算 $f(d)$，然后： [ \text{Ans}(w) = \sum_{d \mid \gcd(w, P)} f(d) ] 因为 $d \mid w$ 且 $d \mid P$ ⇔ $d \mid \gcd(w, P)$。

6. 算法步骤

1. 找出 $P$ 的所有因子（$P \le 10^9$，因子数 $O(10^3)$ 级别）。
2. 对每个因子 $d$，计算 $c(d) = \#\{i : d \mid V_i\}$。
3. $g(d) = 2^{c(d)}$。
4. 用莫比乌斯反演求 $f(d)$： [ f(d) = \sum_{e \mid (P/d)} \mu(e) g(de) ] 这里 $\mu$ 是莫比乌斯函数，对 $P/d$ 的因子求和。
5. 对每个询问 $w$，计算 $\gcd(w, P)$，然后： [ \text{Ans}(w) = \sum_{d \mid \gcd(w, P)} f(d) ]

7. 复杂度

• 因子分解 $P$：$O(\sqrt{P})$。
• 计算 $c(d)$：对每个 $V_i$，枚举它的约数（在 $P$ 的因子中），总复杂度 $O(n \cdot d(P)^2)$ 可能太大？但 $d(P)$ 小，$n$ 大时，我们可以对每个 $d$ 直接检查 $d \mid V_i$，复杂度 $O(n \cdot d(P))$，可接受。
• 莫比乌斯反演：$O(d(P)^2)$ 可接受。
• 回答询问：$O(q \cdot d(P))$。

8. 样例验证

样例：

n=3, q=3, P=6
V = [1, 3, 4]
w = [5, 2, 3]

$P=6$ 的因子：1,2,3,6。

计算 $c(d)$：

• d=1: 所有 V_i 都整除 1，c=3
• d=2: V_i 中 4 整除 2？4%2=0，还有？1%2=1 不整除，3%2=1 不整除，所以只有 {4}，c=1
• d=3: 3 整除 3，其他不整除，c=1
• d=6: 无，c=0

$g(d) = 2^{c(d)}$： g(1)=8, g(2)=2, g(3)=2, g(6)=1

莫比乌斯函数（对 6 的因子）： μ(1)=1, μ(2)=-1, μ(3)=-1, μ(6)=1

计算 $f(d)$：

• f(1) = μ(1)g(1) + μ(2)g(2) + μ(3)g(3) + μ(6)g(6)
  = 1*8 + (-1)*2 + (-1)2 + 11 = 8 - 2 - 2 + 1 = 5
• f(2) = μ(1)g(2) + μ(3)g(6) （因子 e | (P/d=3) 的 e: 1,3）
  = 1*2 + (-1)*1 = 2 - 1 = 1
• f(3) = μ(1)g(3) + μ(2)g(6) （因子 e | (P/d=2) 的 e: 1,2）
  = 1*2 + (-1)*1 = 2 - 1 = 1
• f(6) = μ(1)g(6) = 1

检查： f(1)=5, f(2)=1, f(3)=1, f(6)=1。

询问：

1. w=5: gcd(5,6)=1，所以 Ans = f(1) = 5 ✅
2. w=2: gcd(2,6)=2，Ans = f(1)+f(2) = 5+1=6 ✅
3. w=3: gcd(3,6)=3，Ans = f(1)+f(3) = 5+1=6 ✅

与样例输出一致。

9. 总结

本题核心是将“子集生成模重量”问题转化为子群生成问题，利用 $\gcd$ 结构，用莫比乌斯反演计数子集数，最后通过因子求和回答询问。