408222: GYM103059 C Chess Tournament

Vivek is attending a chess tournament for the first time in many years! His hope are high, but he is also very realistic about his chances to win. He wants to determine the probability that he wins the tournament. Winning the tournament means that he has more points than any other individual player.

In this amateur USCF chess tournament, every single person has a rating ranging from $$$1000$$$ to $$$2000$$$ inclusive, so each match is by no means entirely one-sided. If two people $$$A$$$ and $$$B$$$ with ratings $$$r_A$$$ and $$$r_B$$$ respectively play each other, for the purposes of Vivek's estimations, the probability that $$$A$$$ wins is $$$\dfrac{r_A}{r_A + r_B}$$$, while the probability that $$$B$$$ wins is $$$\dfrac{r_B}{r_A + r_B}$$$, assuming that draws are not in the picture.

The tournament organizers decided that since this was a relatively small chess tournament with only $$$n$$$ participants one week before the tournament started, the format of the tournament will be round robin. Since the tournament directors do not like draws, in a slightly different twist, each pair of players instead of playing each other once, play each other twice. Player $$$A$$$ gets a point if they can defeat player $$$B$$$ in the first match they play, and player $$$B$$$ gets a point if they can defeat player $$$A$$$ in the second match they play. In this slightly different format, Vivek assumes that probability that player $$$A$$$ wins the first match is still $$$\dfrac{r_A}{r_A + r_B}$$$, andthe probability that $$$B$$$ wins the second match is $$$\dfrac{r_B}{r_A + r_B}$$$.

Now, given this tournament style, help Vivek determine the probability that he can be expected to win the tournament! Since the answer will be of the form $$$\dfrac{n}{d}$$$, where $$$n$$$ and $$$d$$$ can be very large, output instead $$$nd^{-1} \mod 10^9 + 7$$$, where $$$d^{-1}$$$ is the modular inverse of $$$d$$$, or the number such that $$$d \cdot d^{-1} \equiv 1 \pmod{10^9 + 7}$$$.

The first line of the input will contain $$$n$$$ ($$$1 \le n \le 250$$$), the number of participants in the chess tournament.

The next line will contain $$$e_v$$$, Vivek's ELO.

The remaining $$$n - 1$$$ lines will each contain an ELO of a participant in the tournament. It is given that for all participants, we have that the ELO $$$e \in [1000, 2000]$$$.

Output $$$nd^{-1} \mod 10^9 + 7$$$, where $$$\dfrac nd$$$ is the probability that Vivek wins the chess tournament, given his assumptions.

2
1500
1000

520000004

In the sample, Vivek has an ELO of 1500, while his one opponent has an ELO of 1000. He has to win both the first game to get his point, and not lose the second game to ensure that his opponent does not tie him. The probability that he wins one match is $$$\dfrac{1500}{1500 + 1000} = \dfrac 35$$$, so the probability of winning both matches is $$$\left( \dfrac 35 \right)^2 = \dfrac{9}{25}$$$. Here, we have $$$25^{-1} \mod 10^9 + 7 = 280000002$$$, and so $$$nd^{-1} \mod 10^9 + 7 = 9 \cdot 280000002\mod 10^9 + 7 = 520000004$$$.