32469번 - Mukjjippa 다국어

문제

Two players A and B are playing a game called mukjjippa.

The game consists of several turns.

At the $i$-th turn (1ドル\le i\le n$):

• Each player chooses exactly one from $\{\mathrm R,\mathrm S,\mathrm P\}$ (meaning rock, scissors, and paper, respectively).
• Let $X_i$ and $Y_i$ be the choices of A and B, respectively.
• If $(X_i,Y_i)\in\{(\mathrm R,\mathrm S) ,(\mathrm S,\mathrm P) ,(\mathrm P,\mathrm R)\},ドル then A becomes an attacker for the $(i+1)$-th turn and the game continues.
• Otherwise, if $(X_i,Y_i)\in\{(\mathrm R,\mathrm P) ,(\mathrm S,\mathrm R) ,(\mathrm P,\mathrm S)\},ドル then B becomes an attacker for the $(i+1)$-th turn and the game continues.
• Otherwise, if there is an attacker for the $i$-th turn, then the attacker becomes a winner and the game ends.
• Otherwise, there is no attacker for the $(i+1)$-th turn and the game continues.

Note that there is no attacker for the first turn.

If the game does not end until the beginning of the $(n+1)$-th turn, nobody is a winner.

The probability distribution of each choice is given. All choices are independent.

Find the probability that A wins.

입력

The first line contains an integer $n$.

The $i$-th of the next $n$ lines contains three integers $r_i,ドル $s_i,ドル and $p_i$. This means that the probabilities that $X_i$ is $\mathrm R,ドル $\mathrm S,ドル and $\mathrm P$ are $\frac{r_i}{r_i+s_i+p_i},ドル $\frac{s_i}{r_i+s_i+p_i},ドル and $\frac{p_i}{r_i+s_i+p_i},ドル respectively.

The $i$-th of the next $n$ lines contains three integers $r_i',ドル $s_i',ドル and $p_i'$. This means that the probabilities that $Y_i$ is $\mathrm R,ドル $\mathrm S,ドル and $\mathrm P$ are $\frac{r_i'}{r_i'+s_i'+p_i'},ドル $\frac{s_i'}{r_i'+s_i'+p_i'},ドル and $\frac{p_i'}{r_i'+s_i'+p_i'},ドル respectively.

출력

Let $\frac{x}{y}$ be the probability that A wins, where $x$ and $y$ are coprime integers, and $x\ge 0$ and $y>0$.

Print the integer $z$ such that $yz\equiv x\pmod{998,円 244,円 353}$ and 0ドル\le z<998,円 244,円 353$.

It can be proved that such an integer $z$ always exists and is uniquely determined, under the constraints of this problem.

제한

• 1ドル\le n\le 2\times 10^5$
• 0ドル\le r_i,s_i,p_i\le 10^6$ (1ドル\le i\le n$)
• $r_i+s_i+p_i>0$ (1ドル\le i\le n$)
• 0ドル\le r_i',s_i',p_i'\le 10^6$ (1ドル\le i\le n$)
• $r_i'+s_i'+p_i'>0$ (1ドル\le i\le n$)

노트