Problem Description

Xiao C has recently become addicted to a game. Now, in the game, Xiao C has a hero with health $x$; the enemy also has a hero with health $y$. In addition, there are $k$ soldiers with health values $a_1,a_2,\cdots,a_k$. Xiao C now plans to use a skill called “Burning Scepter”.

“Burning Scepter” will, each time, uniformly at random select one living character (hero or soldier), reduce its health by $10$, and then if that character’s health is less than or equal to $0$, the character dies and will no longer be selected by “Burning Scepter”. “Burning Scepter” repeats the above operation until any hero dies. Xiao C wants to know the probability that, after using “Burning Scepter”, the enemy hero dies (that is, Xiao C’s hero survives). To avoid precision errors, you only need to output the result modulo a prime $p$, as described in the output format.

Input Format

The input contains multiple test cases.

The first line contains a positive integer $T$, indicating the number of test cases.

Then follow $T$ test cases. For each test case, the first line contains four non-negative integers $x$, $y$, $p$, $k$, representing Xiao C’s hero’s health, the enemy hero’s health, the modulus, and the number of soldiers.

The second line contains $k$ positive integers $a_1,a_2,\cdots,a_k$, representing the health of each soldier.

Output Format

For each test case, output one line with one non-negative integer, representing the remainder of the answer modulo the prime $p$.

It can be proven that the answer is always a rational number. Let the answer be $a/b$ (where $a$ and $b$ are coprime positive integers). If the number you output is $x$, then you must ensure that $a$ is congruent to $b\times x$ modulo $p$; that is, $x \equiv a\times b^{-1} \pmod p$, where $b^{-1}$ denotes the modular inverse of $b$ modulo $p$.

6
1 10 101 0
100 1 101 0
50 30 4903 2
1 1
987 654 233 1
321
1000000000 999999999 233 3
1 2 3
1000000000 999999999 3 3
1 2 3

51
37
1035
118
117
2

Hint

【Sample Explanation】 For the first test case, the required probability is the probability that “Burning Scepter” reduces the enemy hero’s health by $10$ on the very first time, which is $1/2$. $2 \times 51$ modulo $101$ leaves a remainder of $1$.

For the second test case, the answer is $1023/1024$, and $1024 \times 37$ is congruent to $1023$ modulo $101$.

For the third test case, the answer is $99/128$.

【Test Case Scale and Assumptions】

For $10\%$ of the test cases, $x, y, a_1,\cdots, a_k \le 10$.

For $20\%$ of the test cases, $x, y, a_1,\cdots, a_k \le 100$.

For $50\%$ of the test cases, $x, y, a_1,\cdots, a_k \le 1000$.

For all test cases, $1\leq T\leq 100$, $1 \le x, y, a_1,\cdots, a_k \le 10^9$, $3 \le p \le 10000$ and $p$ is a prime, $0 \le k \le 10$.

Lanqiao Cup 2019 National Contest, Group B, Problem J.

Translated by ChatGPT 5