Description

Qinghe is playing a game. They have $n$ clumps of dandelions, where the $i$-th clump has $s_i$ flowers. These dandelions have a magical property: given a constant $\sigma \in (0,1)$, from $x$ dandelions they split off $\lfloor \sigma x \rfloor$ as one group, and the remaining $x-\lfloor \sigma x \rfloor$ continue splitting, until the split-off group has no dandelions, i.e. $\lfloor \sigma x \rfloor=0$. They call this phenomenon "renxing" (stubbornness).

Now each clump of dandelions shows this "renxing" phenomenon. The game rules are as follows: starting from Qing, the two players take turns to travel. One travel means choosing one clump of dandelions and blowing away some flowers in the first group of this clump. You must blow away at least one, and at most the size of the first group, i.e. you cannot blow away any dandelions outside the first group. When the first group becomes empty, the next group becomes the first group. If a clump has only one group of dandelions left, then this clump can no longer be chosen. When no clump can be chosen, the game ends, and the player whose turn it is loses.

They want to know: if, on Qing’s first travel, she first chooses uniformly at random one clump of dandelions that can be operated on, and then uniformly at random chooses the number of flowers to blow away, and after that both players play optimally, what is the value of Qing’s win probability $x \bmod 20190816170251$?

The difference from vol.2 is that after part of the dandelions are blown away, they will not regroup.

Input Format

The first line contains two positive integers $id,n$, where $id$ denotes the Subtask number.

The second line contains $n$ positive integers; the $i$-th one is $s_i$.

If $id>3$, the third line contains two positive integers $p,q$ meaning $\sigma=\dfrac{p}{q}$.

Output Format

Output one integer on one line, which is Qing’s win probability $x \bmod{20190816170251}$.

4 3
1 1 1
1 6

0

6 3
1 7 3
1 3

5047704042563

Hint

Brief statement:

There are $n$ clumps of dandelions. The $i$-th clump has $s_i$ flowers. Given a real number $\sigma$, each clump is split into several groups. The $j$-th group has $t_j$ flowers, and satisfies $t_j=\left\lfloor \sigma\left(s_i - \sum\limits_{k=1}^{j-1}t_k\right) \right\rfloor$. When $t_j=0$, no more groups are formed. Two players alternate moves. Each move, a player may choose one clump of dandelions, and choose an integer $c \in t_j$, and blow away $c$ flowers from this clump, changing $t_j$ into $t_j-c$, where $j$ is the smallest positive integer such that $t_j \neq 0$ in this clump before the move. You must blow away at least one. If you cannot operate, you lose. Find the value of the first player’s win probability $x \bmod{20190816170251}$, under the process that the first player’s first move is: uniformly choose any operable clump of dandelions, then uniformly choose the number of flowers to blow away, and after that both players play optimally.

Sample explanation:

For sample $1$, Qing cannot make any move, so the win probability is $0$.

For sample $2$, the initial position is $\{0;1\},\{2,1,1,1,0;2\},\{1,0;2\}$. Qing can choose the $2$-nd clump, and among two possible moves, choose to blow away $2$ flowers, resulting in $\{0;1\},\{1,1,1,0;2\},\{1,0;2\}$. If she chooses the $3$-rd clump, there is no winning strategy. Also, the $1$-st clump cannot be chosen. Therefore the total win probability is $\dfrac{\frac{1}{2}+0}{2}=\dfrac{1}{4}$.

Constraints:

This problem uses bundled testdata. The score and limits for each Subtask are as follows.

For $100\%$ of the data, $1 \le n \le 3 \times 10^5,1 \le s_i \le 10^{10},1 \le p<q \le 10^9$.

The input size is large. You may use the fast input template from the contest statement to speed up reading.

Translated by ChatGPT 5