Creatnx has $n$ mirrors, numbered from $1$ to $n$. Every day, Creatnx asks exactly one mirror "Am I beautiful?". The $i$-th mirror will tell Creatnx that he is beautiful with probability $\frac{p_i}{100}$ for all $1 \le i \le n$.

Creatnx asks the mirrors one by one, starting from the $1$-st mirror. Every day, if he asks $i$-th mirror, there are two possibilities:  The $i$-th mirror tells Creatnx that he is beautiful. In this case, if $i = n$ Creatnx will stop and become happy, otherwise he will continue asking the $i+1$-th mirror next day;  In the other case, Creatnx will feel upset. The next day, Creatnx will start asking from the $1$-st mirror again. 

You need to calculate the expected number of days until Creatnx becomes happy.

This number should be found by modulo $998244353$. Formally, let $M = 998244353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.


-----Input-----

The first line contains one integer $n$ ($1\le n\le 2\cdot 10^5$) — the number of mirrors.

The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq 100$).


-----Output-----

Print the answer modulo $998244353$ in a single line.


-----Examples-----
Input
1
50

Output
2

Input
3
10 20 50

Output
112



-----Note-----

In the first test, there is only one mirror and it tells, that Creatnx is beautiful with probability $\frac{1}{2}$. So, the expected number of days until Creatnx becomes happy is $2$.

Difficulty: HARD
Tags: Dynamic programming

Data structures

Mathematics

Probability
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
def main():
	m = 998244353
	n = int(input())
	pp = map(int, input().split())
	probb = 100
	num = 0
	for (i, p) in enumerate(pp, 1):
		probu = (100 - p) * probb % m
		probb = p * probb % m
		num = (num * 100 + i * probu) % m
	num = (num + n * probb) % m
	print(num * pow(probb, m - 2, m) % m)
main()


prime = 998244353

def power(x, y, prime):
	b = bin(y)[2:]
	start = x
	answer = 1
	for i in range(len(b)):
		b2 = b[len(b) - 1 - i]
		if b2 == '1':
			answer = answer * start % prime
		start = start * start % prime
	return answer

def process(A):
	P = 100
	Q = 1
	for p in A[:-1]:
		Q = p * Q % prime
		P = 100 * (P + Q) % prime
	Q = Q * A[-1] % prime
	Qinv = power(Q, prime - 2, prime)
	answer = P * Qinv % prime
	return answer
n = int(input())
A = [int(x) for x in input().split()]
print(process(A))


n = int(input())
exp = 0
M = 998244353
for pi in map(int, input().split()):
	exp = (exp + 1) * 100 * pow(pi, M - 2, M) % M
print(int(exp % M))


import sys
input = sys.stdin.readline
mod = 998244353
n = int(input())
p = list(map(int, input().split()))
a = pow(100, n, mod)
b = pow(100, mod - 2, mod)
x = a
y = 1
for i in range(n - 1):
	a = a * b % mod
	y = y * p[i] % mod
	x = (x + a * y) % mod
y = y * p[n - 1] % mod
y_inv = pow(y, mod - 2, mod)
print(x * y_inv % mod)


def solve():
	s = input()
	if 'aa' in s or 'bb' in s or 'cc' in s:
		print(-1)
		return
	syms = s + '@'
	ans = ['@']
	for (i, sym) in enumerate(s):
		if sym != '?':
			ans.append(sym)
			continue
		for x in 'abc':
			if x != ans[-1] and x != syms[i + 1]:
				ans.append(x)
				break
	print(''.join(ans[1:]))

def solveb():
	n = int(input())
	perm = [int(x) for x in input().split()]
	num___idx = [-1 for _ in range(n + 1)]
	for (i, num) in enumerate(perm):
		num___idx[num] = i
	curr_max = -1
	curr_min = 2 * n
	num___pretty = [0 for _ in range(n + 1)]
	for num in range(1, n + 1):
		curr_max = max(num___idx[num], curr_max)
		curr_min = min(num___idx[num], curr_min)
		if curr_max - curr_min + 1 == num:
			num___pretty[num] = 1
	print(*num___pretty[1:], sep='')

def solvec():
	n = int(input())
	rank___problems_nr = [int(x) for x in input().split()]
	weird_prefsums = [0]
	last_num = rank___problems_nr[0]
	for num in rank___problems_nr:
		if num != last_num:
			last_num = num
			weird_prefsums.append(weird_prefsums[-1])
		weird_prefsums[-1] += 1
	gold = weird_prefsums[0]
	silvers = 0
	i = 1
	for i in range(1, len(weird_prefsums)):
		x = weird_prefsums[i]
		if x - gold > gold:
			silvers = x - gold
			break
	bronzes = 0
	for j in range(i, len(weird_prefsums)):
		x = weird_prefsums[j]
		if x > n / 2:
			break
		if x - gold - silvers > gold:
			bronzes = x - gold - silvers
	if bronzes == 0 or silvers == 0:
		print(0, 0, 0)
		return
	print(gold, silvers, bronzes)

def solved():
	(a, b, c, d) = (int(x) for x in input().split())
	ab_len = min(a, b)
	a -= ab_len
	b -= ab_len
	cd_len = min(c, d)
	c -= cd_len
	d -= cd_len
	if a == 1 and cd_len == 0 and (d == 0) and (c == 0):
		print('YES')
		print('0 1 ' * ab_len + '0')
		return
	if d == 1 and ab_len == 0 and (a == 0) and (b == 0):
		print('YES')
		print('3 ' + '2 3 ' * cd_len)
		return
	if a > 0 or d > 0:
		print('NO')
		return
	cb_len = min(b, c)
	b -= cb_len
	c -= cb_len
	if b > 1 or c > 1:
		print('NO')
		return
	print('YES')
	print('1 ' * b + '0 1 ' * ab_len + '2 1 ' * cb_len + '2 3 ' * cd_len + '2' * c)

def get_me(prob, mod):
	return 100 * pow(prob, mod - 2, mod) % mod

def solvee():
	n = int(input())
	mod = 998244353
	idx___prob = [int(x) for x in input().split()]
	curr_me = get_me(idx___prob[0], mod)
	for prob in idx___prob[1:]:
		me = get_me(prob, mod)
		curr_me *= me
		curr_me %= mod
		curr_me += me
		curr_me %= mod
	print(curr_me)

def __starting_point():
	solvee()
__starting_point()


n = int(input())
a = list(map(int, input().split()))
mod = 998244353
rng = 1100
inv = [0, 1]
for i in range(2, rng):
	inv.append(pow(i, mod - 2, mod))
acc = [0] * n
acc[-1] = 100 * inv[a[-1]]
for i in range(n - 1)[::-1]:
	acc[i] = acc[i + 1] * 100 * inv[a[i]] % mod
print(sum(acc) % mod)


import sys
input = sys.stdin.readline
MOD = 998244353
n = int(input())
a = [int(item) for item in input().split()]
A = 0
B = 0
child = 1
bases = []
base = 1
for i in range(n + 10):
	bases.append(base)
	base *= 100
	base %= MOD
for (i, item) in enumerate(a):
	A += child * (100 - item) * bases[n - i - 1]
	A %= MOD
	B += child * (100 - item) * bases[n - i - 1] * (i + 1)
	B %= MOD
	child *= item
	child %= MOD
B += child * n
ans = B * pow(bases[n] - A, MOD - 2, MOD)
ans %= MOD
print(ans)


mod = 998244353
n = int(input())
p = list(map(int, input().split()))
i100 = pow(100, mod - 2, mod)
p = [i * i100 % mod for i in p]
top = 1
for i in range(n - 2, -1, -1):
	top *= p[i]
	top += 1
	top %= mod
bot = 1
for i in range(n):
	bot *= p[i]
	bot %= mod
ans = top * pow(bot, mod - 2, mod) % mod
print(ans)


import os
N = int(300000.0 + 233)
MOD = 998244353
ans = []
for i in range(N):
	ans.append(0)

def fp(x, y):
	res = 1
	while y:
		if y & 1:
			res = res * x
			res %= MOD
		x *= x
		x %= MOD
		y >>= 1
	return res
inv = fp(100, MOD - 2)
n = int(input())
dig = list(map(int, input().split()))
for i in range(1, n + 1):
	x = dig[i - 1]
	x *= inv
	x %= MOD
	ans[i] = (1 + ans[i - 1]) % MOD * fp(x, MOD - 2) % MOD
print(ans[n])


import sys
MOD = 998244353

def powmod(a, b):
	if b == 0:
		return 1
	res = powmod(a, b // 2)
	res *= res
	res %= MOD
	if b & 1:
		res *= a
		res %= MOD
	return res

def inv(n):
	return powmod(n, MOD - 2)
_100 = inv(100)
n = int(input())
p = list(map(lambda x: int(x) * _100 % MOD, input().split()))
if n == 1:
	print(inv(p[0]))
	sys.exit(0)
pp = [0] * n
pp[0] = p[0]
for i in range(1, n):
	pp[i] = pp[i - 1] * p[i] % MOD
k = 0
for i in range(0, n - 1):
	c = inv(pp[n - 2])
	if i:
		c *= pp[i - 1]
		c %= MOD
	k += c
	k %= MOD
res = (k + 1) * inv(p[-1])
res %= MOD
print(res)


from sys import stdin, stdout
read = lambda : map(int, stdin.readline().split())
I = lambda : stdin.readline()
m = 998244353
n = int(I())
arr = tuple(read())
p = 1
fac = 1
s1 = s2 = 0
pows = [1]
for i in range(n):
	pows.append(pows[-1] * 100 % m)
for (ind, i) in enumerate(arr):
	fac = p * (100 - i) * pows[n - ind - 1]
	s1 = (s1 + fac * (ind + 1)) % m
	s2 = (s2 + fac) % m
	p = p * i % m
s1 = (s1 + p * n) % m
s0 = pow(100, n, m)
(p, q) = (s1, s0 - s2)
(div, mod) = divmod(p, q)
if mod == 0:
	print(div)
else:
	q1 = pow(q, m - 2, m)
	print(p * q1 % m)


n = int(input())
p = list(map(int, input().split()))
ans = 0
size = 998244353
for p in p:
	ans = (ans + 1) % size
	ans = ans * 100 % size * pow(p, size - 2, size) % size
print(ans)


N = int(input())
P = list(map(int, input().split()))
mod = 998244353
p = 0
q = 1
for i in range(N):
	(p, q) = (100 * (p + q) % mod, P[i] * q % mod)
print(p * pow(q, mod - 2, mod) % mod)


prime = 998244353

def power(x, y, prime):
	b = bin(y)[2:]
	start = x
	answer = 1
	for i in range(len(b)):
		b2 = b[len(b) - 1 - i]
		if b2 == '1':
			answer = answer * start % prime
		start = start * start % prime
	return answer

def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	if b % a == 0:
		return a
	return gcd(b % a, a)

def add(f1, f2):
	(p1, q1) = f1
	(p2, q2) = f2
	num = p1 * q2 + p2 * q1
	den = q1 * q2
	g = gcd(num, den)
	return [num // g, den // g]

def mult(f1, f2):
	(p1, q1) = f1
	(p2, q2) = f2
	num = p1 * p2
	den = q1 * q2
	g = gcd(num, den)
	return [num // g, den // g]

def process(A):
	num = 100
	den = 1
	for p in A[:-1]:
		den = p * den
		num = 100 * (num + den)
		(num, den) = (num % prime, den % prime)
	den = den * A[-1] % prime
	(P, Q) = (num % prime, den % prime)
	Qinv = power(Q, prime - 2, prime)
	answer = P * Qinv % prime
	return answer
n = int(input())
A = [int(x) for x in input().split()]
print(process(A))


mod = 998244353

def pow_(x, p, mod):
	if p == 1:
		return x % mod
	tmp = pow_(x, p // 2, mod)
	if p % 2 == 0:
		return tmp * tmp % mod
	else:
		return tmp * tmp * x % mod

def reverse(x, mod):
	return pow_(x, mod - 2, mod)
n = int(input()) + 1
p = [0] + list(map(int, input().split()))
dp = [0] * n
rev = [0] * 101
for i in range(1, 101):
	rev[i] = reverse(i, mod)
for i in range(1, n):
	dp[i] = (dp[i - 1] + 1) * 100 * rev[p[i]] % mod
print(dp[-1])


M = 998244353

def gcd(a, b):
	if a == 0:
		return (0, 1)
	(x, y) = gcd(b % a, a)
	return (y - b // a * x, x)
k = input()
probs = list(map(int, input().split(' ')))
(num, denum) = (0, 1)
for p in probs:
	num = (num + denum) * 100 % M
	denum = denum * p % M
(inv, _) = gcd(denum, M)
print(num * inv % M)


mod = 998244353

def inv_mod(n):
	return pow(n, mod - 2, mod)

def frac_mod(a, b):
	return a * inv_mod(b) % mod
n = int(input())
a = input().split()
res = 0
for v in a:
	res = (res + 1) * 100 * inv_mod(int(v)) % mod
print(res)


from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353

def factors(n):
	return sorted(list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def st():
	return input().rstrip('\n')

def val():
	return int(input())
n = val()
exp = 0
for pi in li():
	exp = (exp + 1) * 100 * pow(pi, M - 2, M) % M
print(exp)


mod = 998244353

def inv_mod(n):
	return pow(n, mod - 2, mod)
n = int(input())
p = [int(x) for x in input().split()]
res = 0
for i in p:
	res = (res + 1) * 100 * inv_mod(i) % mod
print(res)


MOD = 998244353

def powr(n, N):
	temp = 1
	while N > 0:
		if N % 2 != 0:
			temp = temp * n % MOD
		n = n * n % MOD
		N = N // 2
	return temp % MOD

def MODI(a, b):
	ans = powr(a, b) % MOD
	return ans
n = int(input())
p = [int(x) for x in input().split()]
mul = 1
kk = 1
for i in range(0, len(p)):
	mul = mul * p[i] % MOD
	kk = kk * 100 % MOD
d = MODI(mul, MOD - 2) % MOD
pre = MODI(100, MOD - 2) % MOD
dp = kk * d % MOD
tot = 0
for i in range(0, len(p)):
	tot = (tot + dp) % MOD
	dp = dp * p[i] % MOD
	dp = dp * pre % MOD
print(tot)


M = 998244353
n = input()
p = list(map(int, input().split(' ')))
num = 0
denum = 1
for i in p:
	num = (num + denum) * 100 % M
	denum = denum * i % M
from math import gcd
g = gcd(num, denum)
num = num // g
denum = denum // g
denum = pow(denum, M - 2, M)
print(num * denum % M)


def extended_gcd(aa, bb):
	(lastremainder, remainder) = (abs(aa), abs(bb))
	(x, lastx, y, lasty) = (0, 1, 1, 0)
	while remainder:
		(lastremainder, (quotient, remainder)) = (remainder, divmod(lastremainder, remainder))
		(x, lastx) = (lastx - quotient * x, x)
		(y, lasty) = (lasty - quotient * y, y)
	return (lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1))

def modinv(a, m):
	(g, x, y) = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m
m = 998244353
n = int(input())
p = list(map(int, input().split(' ')))
up = 0
low = 1
for i in range(n):
	up = up + low
	up = up * 100 % m
	low = low * p[i] % m
print(up * modinv(low, m) % m)


import sys
import math
from collections import defaultdict
from collections import deque
from itertools import combinations
from itertools import permutations
input = lambda : sys.stdin.readline().rstrip()
read = lambda : list(map(int, input().split()))

def write(*args, sep='\n'):
	for i in args:
		sys.stdout.write('{}{}'.format(i, sep))
INF = float('inf')
MOD = 998244353
YES = 'YES'
NO = 'NO'
n = int(input())
p = [0] + read()
p = list(map(lambda x: x * pow(100, MOD - 2, MOD) % MOD, p))
A = [0] * (n + 2)
for i in range(2, n + 2):
	A[i] = (A[i - 1] - 1) * pow(p[i - 1], MOD - 2, MOD) % MOD
print((-A[-1] + MOD) % MOD)


mod = 998244353
N = 1000
inverse = [0, 1]
for i in range(2, N + 1):
	inverse.append(-inverse[mod % i] * (mod // i) % mod)
n = int(input())
p = list(map(int, input().split()))
a = [0] * (n + 1)
b = [0] * (n + 1)
a[0] = 1
for i in range(1, n + 1):
	a[i] = 100 * inverse[p[i - 1]] * (a[i - 1] + p[i - 1] * inverse[100] - 1) % mod
	b[i] = 100 * inverse[p[i - 1]] * (b[i - 1] - 1) % mod
ans = -b[n] * pow(a[n], mod - 2, mod) % mod
print(ans)


from math import gcd
MOD = 998244353
n = int(input())
p = list(map(int, input().split(' ')))
num = [0]
denom = [1]
for i in range(n):
	num.append((num[i] + denom[i]) * 100)
	denom.append(denom[i] * p[i])
	GCD = gcd(num[i + 1], denom[i + 1])
	num[i + 1] = num[i + 1] // GCD % MOD
	denom[i + 1] = denom[i + 1] // GCD % MOD
print(num[n] * pow(denom[n], MOD - 2, MOD) % MOD)


import sys
input = sys.stdin.readline
n = int(input())
L = map(int, input().split())
k = 0
c = 1
m = 998244353
counter = 0
for i in L:
	k += c * pow(100, n - counter, m)
	k %= m
	c *= i
	c %= m
	counter += 1

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
p = k % m
q = c % m
print(modInverse(q, m) * p % m)


MOD = 998244353

def power(x, y):
	res = 1
	while y > 0:
		if y & 1:
			res = x * res % MOD
		y = y >> 1
		x = x * x % MOD
	return res
n = int(input())
prob = input().split()
p = power(100, n)
q = 1
for i in range(0, n - 1):
	q = q * int(prob[i]) % MOD
	p = (p + q * power(100, n - i - 1) % MOD) % MOD
q = q * int(prob[n - 1]) % MOD
print(p * power(q, MOD - 2) % MOD)


import sys
input = sys.stdin.readline
mod = 998244353

def extgcd(a, b):
	r = [1, 0, a]
	w = [0, 1, b]
	while w[2] != 1:
		q = r[2] // w[2]
		r2 = w
		w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
		r = r2
		w = w2
	return [w[0], w[1]]

def mod_inv(a, m=mod):
	x = extgcd(a, m)[0]
	return (m + x % m) % m
N = int(input())
A = list(map(int, input().split()))
K = 0
P = 0
Q = 1
for (i, a) in enumerate(A):
	p0 = a * mod_inv(100) % mod
	q0 = (100 - a) * mod_inv(100) % mod
	P = (P + (i + 1) * Q * q0) % mod
	K = (K + Q * q0) % mod
	Q = Q * p0 % mod
inv = (mod + 1 - K) % mod
w = (N * Q + P) % mod
ans = w * mod_inv(inv) % mod
print(ans)


import os, sys
from io import BytesIO, IOBase

def main():
	mod = 998244353
	div = pow(100, mod - 2, mod)
	n = int(input())
	p = list(map(lambda xx: int(xx) * div % mod, input().split()))
	p1 = list(map(lambda xx: 1 - xx + mod if xx > 1 else 1 - xx, p))
	X = 1
	for i in range(n):
		X = X * p[i] % mod
	(an, pr) = (0, 1)
	for i in range(1, n + 1):
		an = (an + i * pr * p1[i - 1]) % mod
		pr = pr * p[i - 1] % mod
	an = (an + n * X) % mod
	an = an * pow(X, mod - 2, mod) % mod
	print(an)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = input()
n = int(n)
md = 998244353
L = list(map(int, input().split()))

def inv(x):
	nonlocal md
	return pow(x, md - 2, md)
ml = 1
ans = 0
for el in reversed(L):
	ml *= 100
	ml *= inv(el)
	ml %= md
	ans += ml
	ans %= md
print(ans)


mod = 998244353
n = int(input())
ar = list(map(int, input().split()))
(m, mul) = (1, [1])
div = pow(100, mod - 2, mod)
for i in ar:
	mul.append(mul[-1] * i * div % mod)
num = 0
den = pow(mul[n], mod - 2, mod)
for i in mul:
	num += i
	num %= mod
print((num * den - 1) % mod)


input()
p = list(map(int, input().split()))
mod = 998244353
f = 0
for i in p:
	f = 100 * (f + 1) * pow(i, mod - 2, mod) % mod
print(f)


from sys import stdin
input = stdin.readline
mod = 998244353
inv = [0] * 103
inv[1] = 1
for i in range(2, 101):
	inv[i] = (mod - mod // i) * inv[mod % i] % mod
n = int(input())
h = [0] * (n + 3)
h[0] = 1
for i in range(1, n + 2):
	h[i] = h[i - 1] * 100 % mod
p = list(map(int, input().split()))
tot = 1 * h[n] % mod
now = 1
iv = 1
for i in range(n):
	if i == n - 1:
		iv = iv * inv[p[i]] % mod
		continue
	now = now * p[i] % mod
	tot += now * h[n - i - 1] % mod
	tot %= mod
	iv = iv * inv[p[i]] % mod
print(tot * iv % mod)


import time
import sys
f = sys.stdin
t1 = time.time()
n = int(f.readline())
MOD = 998244353
prob = list(map(int, f.readline().split()))
num = pow(100, n, MOD)
new_term = num
inv_100 = pow(100, MOD - 2, MOD)
for x in prob[:-1]:
	new_term = new_term * x * inv_100 % MOD
	num = (num + new_term) % MOD
t4 = time.time()
den = new_term * prob[-1] * inv_100
inverse = pow(den, MOD - 2, MOD)
print(num * inverse % MOD)