Dandelion Indignation

In this game, there are (n) clumps of dandelions. The (i)th clump initially contains (s_i) dandelions. Each clump exhibits a curious phenomenon. Given a constant (\sigma\in(0,1)), we partition (s) dandelions as follows:

Set (x=s). While (\lfloor \sigma x\rfloor>0), form a group containing (\lfloor \sigma x\rfloor) dandelions and then update (x) to (x-\lfloor \sigma x\rfloor). That is, the groups are
[ g_1=\lfloor \sigma s\rfloor,\quad g_2=\lfloor \sigma(s- g_1)\rfloor,\quad g_3=\lfloor \sigma(s- g_1-g_2)\rfloor,\dots ]
and the process stops when (\lfloor \sigma x\rfloor=0). We call this property indignation.

Two players, Qing and Qinghe, play a game. They take turns (starting with Qing) performing a "travel" move. A travel move is defined as follows on a clump that has at least two groups (if a clump has only one group it cannot be chosen):

• Select one clump (all clumps with at least two groups are selectable; the first selection is made uniformly at random among these clumps).
• In the chosen clump with groups \((g_1, g_2, g_3,\dots)\), blow away some number (at least one and at most \(g_1\)) of dandelions from the first group. Note that you may only remove dandelions from the first group.
• If after blowing, the first group becomes empty, then it is removed and the next group becomes the first group. Unlike vol.2, the remaining groups are not re‐grouped.

The game proceeds until no clump is selectable. The player whose turn it is when no move is available loses.

Now, suppose that on Qing’s very first travel move, she does not choose her move strategically. Instead, she first picks one selectable clump uniformly at random and then uniformly picks a number between \(1\) and \(g_1\) (the size of the first group) and blows that many dandelions. After this first move the two players play optimally. Let \(x\) be the probability that Qing eventually wins. Output \(x\) modulo \(20190816170251\).

Note: For the purpose of game theory the following observation holds. If a clump originally has groups \((g_1, g_2, \dots, g_k)\) (with \(k\ge 2\)) then its game value (Grundy value) is determined recursively. In fact, if we define a function \[ F(a,X)=\begin{cases} a,&\text{if } X g_2\) the value ends up being \(g_1\) (for a two–group clump) and, more generally, each clump’s value is completely determined by its first group. Hence if we let \(N\) be the XOR of the values \(g_1\) of all selectable clumps then an optimal move on a clump with first group \(g_1\) is one that changes its value to \(N\oplus g_1\.\)

For a clump with first group of size \(g_1\) and second group \(g_2\), a move consists of subtracting \(r\) (with \(1\le r\le g_1\)). The resulting state has value
\[ \text{value} = \begin{cases} g_1 - r,&\text{if } g_1 - r > g_2,\\ g_1 - r - 1,&\text{if } g_1 - r \le g_2. \end{cases} \] A move is winning (i.e. will eventually force a victory with optimal play) if this resulting value equals \(N\oplus g_1\). The overall winning probability is the average, over all selectable clumps and all legal moves on the chosen clump, of the indicator that the move is winning.

Your task is to calculate \(x\) modulo \(20190816170251\).

inputFormat

The first line contains two numbers: an integer (n) and a real number (\sigma) (with (0<\sigma<1)).

The second line contains (n) positive integers (s_1,s_2,\dots,s_n) separated by spaces.

outputFormat

Output a single integer representing Qing’s winning probability (x) modulo (20190816170251). Here, if the answer is a rational number (\frac{p}{q}) in lowest terms, output (p\cdot q^{-1}) modulo (20190816170251).

sample

3 0.3
10 12 5

0