신경망

Art는 UT에서 컴퓨터 과학을 전공하는 학생이다. 지난 두 학기 동안 수십 개의 인턴십에 지원한 끝에, 마침내 꿈에 그리던 일자리를 얻었다. 오스틴의 떠오르는 머신러닝 스타트업에서 신경망을 설계하는 일이다.

신경망은 노드가 층으로 분할된 방향 그래프이다. $i$번째 층의 노드 수를 $A\_i$라 하고 층이 총 $N$개라면, 그래프의 노드 수는 $\sum\_{i=1}^N A\_i$이다. 그래프의 모든 간선은 $i$번째 층의 노드에서 $(i+1)$번째 층의 노드로 향한다. 이런 그래프는 다음과 같이 계산에 쓰인다. 층 1의 노드에 입력이 주어지고, 정보가 그래프의 간선을 따라 마법처럼 흐르고, 층 $N$의 노드에서 출력을 읽는다.

출근 첫날, 상사는 Art에게 신경망의 각 층별 노드 수를 담은 길이 $N$의 배열 $A$를 주고, 간선을 몇 개 추가해 이 신경망을 흥미롭게 만들라고 한다. 신경망이 흥미롭다는 것은, 그래프의 모든 노드 $u$(층 1과 층 $N$의 노드도 포함)에 대해 층 1에서 층 $N$으로 정보가 흐르는 경로 중 $u$를 지나는 경로가 존재한다는 뜻이다.

Art는 주어진 명세로 만들 수 있는 흥미로운 신경망이 아주 많을 수 있다는 것을 깨닫는다. 하지만 일이 너무 모호하다고 상사에게 불평하기 전에, 그런 신경망이 정확히 몇 개인지 알아내는 일을 당신에게 부탁하려 한다. 답이 아주 클 수 있으므로, 소수 $998\,244\,353$으로 나눈 나머지를 출력한다.

그래프의 노드에는 번호가 붙어 있다. 노드 $1, \dots, A\_1$은 층 1에, 노드 $A\_1+1,\dots,A\_1+A\_2$는 층 2에 속하는 식이다. 한쪽 신경망에는 있고 다른 쪽에는 없는 간선이 하나라도 있으면 두 신경망은 다른 것으로 본다.

첫째 줄에 신경망의 층 수 $N$이 주어진다 ($2 \leq N \leq 5 \cdot 10^5$). 둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어지는데, $i$번째 정수는 $i$번째 층의 노드 수 $A\_i$이다. (각 $i$에 대해 $1 \leq A\_i \leq 5 \cdot 10^5$이고, $\sum\_{i=1}^N A\_i \leq 5 \cdot 10^5$이다. 즉, 전체 노드 수는 $5 \cdot 10^5$ 이하이고 각 층에는 노드가 적어도 하나 있다.)

주어진 명세에 대응하는 서로 다른 흥미로운 신경망의 개수를 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.