Description

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$.

Input Format

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 Format

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

2 2
1 4

51

Hint

[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<998244353$.

The detailed constraints are shown in the table below:

Translated by ChatGPT 5