406009: GYM102218 B Buying Piles of Stones

Alice and Bob love playing the classic Nim game, in which the two players take turns removing stones from distinct piles. In each turn, a player must remove a positive number of stones from a single pile. The player that cannot make a move loses the game.

But now there is a problem: they don't have any piles of stones to play with! So, they are thinking of buying some piles of stones in the Nim Store. Nim Store offers piles inside a box, so that its size is unknown until the client pays for it. It is known that there are $$$K$$$ possible sizes for the piles: $$$c_1, c_2, ..., c_k$$$, and all of them can be chosen with the same probability.

Alice always makes the first move when playing with Bob, so she is wondering what is the probability to have a winning strategy, if they buy $$$M$$$ piles of stones, assuming that the number of stones in the piles is equiprobable and the size of the piles is independent from each other.

Help Alice to calculate this probability. It can be shown that it is in the form of a fraction $$$\frac{P}{Q}$$$ where $$$P$$$ and $$$Q$$$ are non-negative integers and $$$Q \neq 0$$$, $$$P \leq Q$$$. Output the value of $$$P*Q^{-1} \mod 998244353$$$.

The first line contains two integers numbers $$$M$$$ and $$$K$$$ ($$$1 \leq M \leq 10^9$$$, $$$1 \leq K < 2^{17}$$$) - the number of piles that Alice and Bob are going to buy and the number of different sizes of the piles.

The second line contains $$$K$$$ different integers numbers $$$c_1, c_2, ..., c_k$$$ ($$$1 \leq c_i < 2^{17}$$$) - the size of piles offered by Nim store.

Print one integer $$$P*Q^{-1}$$$ - the probability that Alice has a winning strategy modulo $$$998244353$$$.

2 2
1 3

499122177

11 1
5

1

7 3
1 2 3

50665352

In the first sample, Alice and Bob are buying two piles, and the possible sizes for them are $$$1$$$ and $$$3$$$. The possible ordered combinations of sizes are $$$(1,3)$$$, $$$(3,1)$$$ $$$(1,1)$$$ and $$$(3,3)$$$. It can be shown that Alice only has a winning strategy in $$$(1,3)$$$ and $$$(3,1)$$$. So, the probability is $$$\frac{1}{2}$$$.