UVA13129 Subsets

艾琳刚学会了如何生成一个集合的所有子集。当集合中元素数量很少时，这个操作非常简单，但如果集合很大呢？她想要练习所学的内容，于是遇到了下面这个问题： 给定一个包含 $N$ 个互不相同的正整数的数组 $a_1, a_2, \dots, a_N$，以及一个底数 $P$。有 $Q$ 次查询，每次查询给出两个下标 $A$ 和 $B$（$1 \le A \le B \le N$）。对于每次查询，她选出数组中位置 $A, A+1, \dots, B$ 上的值，并生成这些值的所有**非空**子集。然后，她对每个子集的元素和求 $P$ 的幂次方，最后将所有幂次结果相加，得到答案。 例如，数组为 $[3, 5, 2, 7]$，查询 $A=1, B=3, P=2$，选出 $3,5,2$，其所有非空子集为 $\{3\},\{5\},\{2\},\{3,5\},\{3,2\},\{5,2\},\{3,5,2\}$。对应的幂次和为： $2^3+2^5+2^2+2^{3+5}+2^{3+2}+2^{5+2}+2^{3+5+2} = 8+32+4+256+32+128+1024 = 1484$。 她很快意识到这个任务非常复杂，于是向你求助，希望你能帮她计算出答案。你愿意帮这个忙吗？

输入包含多组测试数据，每组数据格式如下，处理到文件末尾（EOF）。 每组数据的第一行包含两个整数 $N$ 和 $P$（$1 \le N \le 5 \times 10^5$，$2 \le P \le 10^5$），分别表示数组长度和幂的底数。 第二行包含 $N$ 个正整数 $a_1, a_2, \dots, a_N$（$1 \le a_i \le 10^9$），表示数组元素，保证所有 $a_i$ 互不相同。 第三行包含一个整数 $Q$（$1 \le Q \le 5 \times 10^5$），表示查询次数。 接下来 $Q$ 行，每行包含两个整数 $A, B$（$1 \le A \le B \le N$），表示一次查询的区间。

对于每组测试数据，依次输出该组中每个查询的答案，每个答案占一行。 **每个查询的答案**为区间内所有非空子集的幂次和，由于结果可能非常大，请输出该结果对 $10^9+7$ 取模后的整数。 不同测试数据之间**不需要**额外空行。

## 样例解释 第二组数据中，数组 $[1,2,3]$，$P=3$，查询 $[1,2]$ 的非空子集幂和为 $3^1+3^2+3^{1+2}=3+9+27=39$；查询 $[2,3]$ 为 $3^2+3^3+3^{2+3}=9+27+243=279$。） ## 提示 对于区间 $[A,B]$，考虑所有子集（包括空集）的和可表示为： $$ \prod_{i=A}^{B} (1 + P^{a_i}) $$ 因为每个元素要么不选（贡献 $1$），要么选入子集（贡献 $P^{a_i}$），所有子集的总和即为该乘积。该乘积包含了空集对应的 $1$，而题目要求的是**非空子集**，所以真正的答案为： $$ \left(\prod_{i=A}^{B} (1 + P^{a_i})\right) - 1 $$ 由于答案可能极大，请将答案对 $10^9+7$ 取模后输出。注意取模运算中减法可能需要调整为 $(product - 1 + MOD) \% MOD$。 ## 数据范围 - 单个测试点内所有数据组中 $N$ 的总和不超过 $5 \times 10^5$，$Q$ 的总和也不超过 $5 \times 10^5$。 - $P$ 和 $a_i$ 的范围如输入格式所述。 翻译由 DeepSeek V4 辅助完成