Infinite Backpack Profit

You are given an infinite capacity backpack and n items. The volume of the i-th item is \(a_i\). You also have a lucky number \(p\). If you select a set of items whose total volume is \(k\), then you will obtain a profit of \(p^k\) (note that \(0^0 = 1\)).

There are \(2^n\) ways to choose a subset (possibly empty) of items. Your task is to compute the sum of the profits of all these \(2^n\) selections and output the result modulo \(998244353\).

In other words, if you choose a subset \(S\) of items, its profit is \(p^{\sum_{i\in S}a_i}\). Compute:

[ \sum_{S \subseteq {1,2,\ldots,n}} p^{\sum_{i\in S} a_i} \pmod{998244353}. ]

Hint: This sum can be factorized as \(\prod_{i=1}^{n} \Big(1 + p^{a_i}\Big)\).

inputFormat

The first line contains two integers \(n\) and \(p\) (the number of items and the lucky number) separated by a space.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the volume of each item.

outputFormat

Output a single integer: the sum of the profits of all \(2^n\) subsets modulo \(998244353\).

sample

3 2
1 2 3

135