Description

Qinghe is playing a game. They have $n$ bunches of dandelions, and the $i$-th bunch has $s_i$ flowers.

These dandelions have a magical property: for a given constant $\sigma \in (0,1)$, for $x$ flowers, $\lfloor \sigma x \rfloor$ flowers are split off as one group, and the remaining $x-\lfloor \sigma x \rfloor$ flowers continue to be split in the same way, until the split-off group contains no dandelions, i.e. $\lfloor \sigma x \rfloor=0$. They call this phenomenon "renxing" (stubbornness).

Now each bunch of dandelions has this "renxing" property. The rules are as follows:

Starting from Qing, the two players take turns to make a travel move. One travel move means choosing one bunch of dandelions and blowing away some flowers from the first group of that bunch. You must blow away at least one flower, and at most the size of the first group; that is, 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 bunch has only one group of dandelions left, then this bunch can no longer be chosen. When no bunch 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 chooses uniformly at random one bunch 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 winning probability $x \bmod{20190816170251}$?

The difference from vol.1 is that after a bunch of dandelions is partially blown away, it will be regrouped.

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 per line, representing Qing’s winning probability $x \bmod{20190816170251}$.

4 3
1 1 1
1 6

0

6 3
1 7 3
1 3

15143112127689

Hint

Brief statement:

There are $n$ bunches of dandelions; the $i$-th bunch has $s_i$ flowers. Given a real number $\sigma$, two players move alternately. Each move can choose one bunch of dandelions, and choose an integer $c \in (0,\sigma s]$, then blow away $c$ flowers from that bunch, where $s$ is the number of flowers in that bunch before the move. You must blow away at least one flower. If a player cannot move, that player loses.

Find the value of the first player’s winning probability $x \bmod{20190816170251}$, under the process where on the first move the first player uniformly at random chooses any operable bunch of dandelions and then uniformly at random chooses the number of flowers to blow away, and afterwards both players use optimal strategies.

Sample explanation:

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

For sample $2$, Qing can choose the $2$-nd bunch and, among two possible moves, choose to blow away $2$ flowers to become $1,5,3$; or choose the $3$-rd bunch and choose the only possible move to become $1,7,2$. The $1$-st bunch cannot be chosen. The overall winning probability is $\dfrac{\frac{1}{2}+1}{2}=\dfrac{3}{4}$.

Constraints:

This problem uses bundled testdata. The score and limits of 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 of this problem is large. You may use the fast input template from the contest statement to speed up reading.

Translated by ChatGPT 5