longlongint National Girls' Programmi...
Limits 1s, 512 MB

It is Argentina vs France in the football world cup final of 2022 in a parallel universe.

You are a supporter of Argentina. 120 minutes of play has ended in a draw. So, penalty shootout will begin. You know the scoring probabilities for each of the 22 players on the field. You also know that both teams would send shooters in an optimal order. And the order must be submitted to the referee before the shootout begins. Argentina start first. The rules of penalty shootout are as follows:

  1. Teams take shots alternately.

  2. For any consecutive 11 shots of a team, a player can shoot exactly once.

  3. If both teams have taken equal number of shots and each team has taken at least 5 shots, then the leading team wins. If scores are still tied, they continue shooting until a team wins.

We denote a goal with \checkmark and a miss with ×\times.

The shootout begins. The scorecard after 5 shots per team is:
ARG: \checkmark\checkmark\checkmark×\times\checkmark
FRA: ×\times\checkmark\checkmark\checkmark\checkmark
This means Argentina missed its 4th shot and France missed its 1st shot. The score is tied at 4-4.

You are losing your sanity from the suspense. You know the first 5 shooters went in optimal order which was submitted before the shootout began. Now you calculate the probability of Argentina winning the world cup. This means you calculate it after 5 shots per team was taken and before Argentina’s 6th shot. Print the number modulo 998244353998244353.

Formally, let the probability be an irreducible fraction xy\frac{x}{y}. Print the value xy1x \cdot y^{-1}mod 998244353998244353. Where y1y^{-1} is an integer such that yy11y \cdot y^{-1} \equiv 1 mod 998244353998244353. Input data for this problem was made such that y1y^{-1} exists.

A player might need to take multiple shots in the shootout. The outcome of any shot does not change his scoring probability.

Some possible outcomes of the shootout continuing from the current situation:

ARG: \checkmark\checkmark\checkmark×\times\checkmark×\times
FRA: ×\times\checkmark\checkmark\checkmark\checkmark\checkmark
After 6 shots per team, France lead. So France wins.

ARG: \checkmark\checkmark\checkmark×\times\checkmark \checkmark \checkmark ×\times\checkmark
FRA: ×\times\checkmark\checkmark\checkmark\checkmark \checkmark \checkmark ×\times ×\times
After 9 shots per team, Argentina lead by 7-6. So Argentina wins.

ARG: \checkmark\checkmark\checkmark×\times\checkmark×\times ×\times×\times \checkmark \checkmark\checkmark×\times×\times\checkmark×\times×\times \checkmark \checkmark\checkmark×\times×\times\checkmark\checkmark \checkmark
FRA: ×\times\checkmark\checkmark\checkmark\checkmark ×\times ×\times ×\times\checkmark\checkmark \checkmark×\times×\times\checkmark×\times×\times \checkmark \checkmark\checkmark×\times×\times\checkmark\checkmark×\times
After 24 shots per team, Argentina lead by 14-13. So Argentina wins.


The input consists of 22 lines, each containing 1111 space separated integers.
The ii-th integer Ai(1Ai<100)A_i (1 \leq A_i \lt 100) on the first line indicates that scoring probability for the ii-th player of Argentina is Ai100\frac{A_i}{100}.
The ii-th integer Fi(1Fi<100)F_i (1 \leq F_i \lt 100) on the second line indicates that scoring probability for the ii-th player of France is Fi100\frac{F_i}{100}.
Input is not necessarily given in the optimal shooting order.


Print a single integer, the probability of Argentina winning modulo 998244353998244353.


99 99 99 99 99 99 99 99 99 99 99
1 1 1 1 1 1 1 1 1 1 1

The actual probability is 98019802\frac{9801}{9802}.

41 49 94 58 69 65 98 57 39 7 71
85 5 4 90 8 46 21 75 84 41 93

The actual probability is 805579505474632220365066324411338112123531088532242843736676673393538\frac{8055795054746322203650663244113381}{12123531088532242843736676673393538}. Which is roughly equal to 0.66447596792706460.6644759679270646.

50 50 50 50 50 50 50 50 50 50 50
50 50 50 50 50 50 50 50 50 50 50

The probability is 12\frac{1}{2}.


Login to submit.


0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.