P7223 [RC-04] 01 Knapsack

There is a knapsack with capacity $+\infty$, and you want to put items into it. You have $n$ items, and the $i$-th item has volume $a_i$. You have a lucky number $p$. If the sum of the volumes of the items you put in is $k$, you will get a profit of $p^k$. **In particular, $0^0=1$.** Compute the sum of profits over all $2^n$ ways of choosing items to put into the knapsack. The answer is very large, so output it modulo $998244353$.

The first line contains two integers $n,p$. The next line contains $n$ positive integers $a_1\sim a_n$, describing the volumes of these $n$ items.

Output one integer, the sum of profits over all $2^n$ ways modulo $998244353$.

[Sample Explanation] The answer is $2^0+2^1+2^4+2^5=51$. [Constraints] For all testdata, $1\le n\le 10^6$, $0\le p,a_i