Dandelion Game with Re‐grouping

In this problem, Qing and her friend play a game with n clusters of dandelions. The dandelions in each cluster exhibit a magical property called rénxìng (arbitrariness). In a cluster with s dandelions, the dandelions are repeatedly grouped as follows:

Given a constant \(\sigma \in (0,1)\), when there are \(x\) dandelions remaining in the cluster, one first forms a group of \(\lfloor \sigma x\rfloor\) dandelions. The process then continues with the remaining \(x-\lfloor \sigma x\rfloor\) dandelions until no more group can be formed (i.e. when \(\lfloor \sigma x\rfloor=0\)). Let \(f(s)\) be the total number of groups formed. We say the cluster is movable if and only if \(f(s)\ge2\) (that is, the cluster has at least two groups). Note that if a cluster produces only one group, it cannot be chosen in a move.

The game is played as follows. Starting with Qing, the two players take turns performing a travel. In one travel the player selects a movable cluster (i.e. one currently having at least two groups) and then blows away some dandelions from the first group of that cluster. The player must blow away at least 1 dandelion and at most all \(\lfloor \sigma s\rfloor\) dandelions in the first group. Immediately after some dandelions are blown away from that cluster, the cluster re‐groups its remaining dandelions as described above.

The game ends when no cluster is movable. The player who is about to move in such a situation loses. Unlike the previous version of the problem (vol.1), here the cluster re‐groups its dandelions after a move.

All clusters act as separate subgames. It is natural to analyze each cluster by its Grundy value (or nimber). For a cluster with s dandelions, if it is movable (i.e. \(f(s)\ge2\)), the allowed moves are to subtract any \(k\) (\(1\le k\le \lfloor \sigma s\rfloor\)) dandelions and then re‐group the remaining \(s-k\) dandelions. We define the Grundy value \(g(s)\) by the recurrence:

[ g(s)=\begin{cases}0, & \text{if } f(s)<2,\ \operatorname{mex}{g(s-k): 1\le k\le \lfloor \sigma s\rfloor}, & \text{otherwise.} \end{cases} ]

The overall game is the disjunctive sum of the clusters, with the total nim‐sum \(G=\bigoplus_{i=1}^n g(s_i)\).

However, there is one twist. Although both players play optimally after the first move, Qing’s first travel is performed in a random manner: she first selects one movable cluster uniformly at random among all movable clusters, and then among that cluster she selects a valid move (i.e. a number \(k\) satisfying \(1\le k\le \lfloor \sigma s\rfloor\)) uniformly at random. Let the total number of legal moves (across all movable clusters) be \(T\) and the number of moves that lead to a position that is winning for Qing (after the move, it becomes her opponent’s turn on a losing position) be \(W\). Then Qing's winning probability is \(\frac{W}{T}\). Since the answer can be a rational number, output the value of \(\frac{W}{T}\) modulo \(20190816170251\) (by computing \(W \cdot T^{-1}\) modulo \(20190816170251\)). You may assume that \(20190816170251\) is prime so that the inverse exists.

Input Format: The first line contains two numbers: an integer \(n\) (the number of clusters) and a real number \(\sigma\) (with \(0<\sigma<1\)). The second line contains \(n\) positive integers \(s_1,s_2,\ldots,s_n\), where \(s_i\) is the number of dandelions in the \(i\)th cluster.

Output Format: Output an integer, representing Qing's winning probability \(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₁, s₂, …, sₙ.

outputFormat

Output an integer representing Qing's winning probability (\frac{W}{T}) modulo (20190816170251), where W is the number of winning moves and T is the total number of legal moves in Qing’s first travel.

sample

3 0.5
3 5 7

Output depends on analysis