I. Mukjjippa
time limit per test
2 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

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.

Input

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.

Output

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

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

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

Scoring
  • $$$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 \gt 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' \gt 0$$$ ($$$1 \le i \le n$$$)
Examples
Input
2
1 0 0
0 1 0
0 1 0
0 1 0
Output
1
Input
2
1 1 1
1 1 1
1 1 1
1 1 1
Output
443664157