No.2792 Security Cameras on Young Diagram
Problem Statement
Hakoboshi loves Young diagrams.
Consider the Young diagram of a non-increasing sequence $A=(A_1,A_2,\ldots,A_N)$. That is, in the $i$-th row from the top, $A_i$ squares are placed, aligned to the left.
You place downward-facing or rightward-facing cameras on cells of the Young diagram. If a downward-facing camera is placed on a cell, that cell itself and the cells below it are monitored. If a rightward-facing camera is placed on a cell, that cell itself and the cells to the right of it are monitored.
Find the number of ways to place cameras so that all of the following conditions are satisfied, modulo $998244353$.
- For each cell, the number of cameras on that cell is $0$ or $1$.
- Every cell is monitored by some camera.
- A cell containing a camera is not monitored by any other camera.
Constraints
- $1\le N\le 10^5$
- $1\le A_i\le 10^5$
- $A_1\ge A_2\ge\cdots\ge A_N$
- All input values are integers.
Input
The input is given from standard input in the following format.$N$ $A_1$ $A_2$ $\cdots$ $A_N$
Output
Output the answer.
Sample
Sample 1
Input
2 3 2
Output
7
Sample 2
Input
3 111 22 3
Output
375
Sample 3
Input
6 3 2 2 1 1 1
Output
14
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。