[RC-04] 01 背包

有一个容积为 $+\infty $ 的背包，你要往里面放物品。 你有 $n$ 个物品，第 $i$ 个体积为 $a_i$。 你有一个幸运数字 $p$，若放入的物品体积和为 $k$，你会得到 $p^k$ 的收益。**特别地，$0^0=1$。** 求所有 $2^n$ 种放入物品的方案的收益和。答案很大，因此请输出它对 $998244353$ 取模的值。

第一行两个整数 $n,p$。 接下来一行 $n$ 个正整数 $a_1\sim a_n$，描述这 $n$ 个物品的体积。

输出一个整数，为所有 $2^n$ 种方案的收益和对 $998244353$ 取模的值。

2 2
1 4

51

【样例解释】 答案为 $2^0+2^1+2^4+2^5=51$。 【数据范围】 对于所有数据，$1\le n\le 10^6$，$0\le p,a_i<998244353$。 详细数据范围如下表： | 测试点编号 | $n$ | $p$ | $\sum_{i=1}^na_i$ | 每测试点分数 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | | $=0$ | | $2$ | | $2\sim 5$ | $\le 22$ | | | $6$ | | $6\sim 9$ | $\le 1000$ | | $\le 1000$ | $6$ | | $10\sim 14$ | $\le 100000$ | | $\le 100000$ | $5$ | | $15$ | | | | $25$ |