Gacha 101

각 $i = 1, 2, \dots, N$에 대해 숫자 $i$가 적힌 공이 $A_i$개 있다. 모든 공을 상자에 넣고 잘 섞는다. 문자열 $s$는 처음에 $N$개의 "0"으로 이루어져 있다. 상자에서 공을 하나씩 균등한 확률로 무작위로 꺼낸다. 숫자 $i$가 적힌 공을 꺼내면 $s$의 $i$번째 문자가 "1"로 바뀐다. 이미 "1"이었다면 그대로 둔다. 이 과정 중 어느 순간에든 $s$가 "101"을 연속된 부분 문자열로 포함하게 될 확률을 구하라. 답은 $998\,244\,353$으로 나눈 나머지로 출력한다.

입력은 다음 형식으로 주어지는 테스트 케이스 하나이다.

$N$

$A_1$ $A_2$ $\dots$ $A_N$

첫째 줄에 정수 $N$이 주어진다. 단, $1 \le N \le 200\,000$이다. 둘째 줄에는 양의 정수 $A_1, A_2, \dots, A_N$이 주어진다. 각 $i$ ($1 \le i \le N$)에 대해 $A_i$는 숫자 $i$가 적힌 공의 개수이다. 모든 $A_i$의 합은 $998\,244\,353$보다 작다.

구한 확률을 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.

법 $998\,244\,353$에서 확률을 구하는 방법.

구하는 확률은 항상 유리수이다. 이 문제의 제약 조건에 따르면, 확률을 기약분수 $\frac{y}{x}$로 나타내었을 때 $x$는 $998\,244\,353$으로 나누어떨어지지 않는다. 이때 $y \equiv xz \pmod{998\,244\,353}$을 만족하는 $0 \le z < 998\,244\,353$이 유일하게 존재한다. 이 $z$를 출력한다.