/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 4 点
問題文
1 円硬貨, 2 円硬貨, \dots, N 円硬貨があります。i 円硬貨は A_i 枚あります。同じ金額の硬貨同士は区別できません。
これらの硬貨を用いて N 円ちょうどを支払う方法の個数を 998244353 で割った余りを求めてください。ただし、2 つの払い方は、払う枚数が 2 つの払い方の間で異なる硬貨が存在する時に別々に数えます。
制約
- 1 \leq N \leq 2.5 \times 10^5
- 1 \leq A_i \leq N
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
3 1 2 3
出力例 1
2
3 円ちょうどを支払う方法は次の 2 通りです。
- 1 円硬貨と 2 円硬貨を 1 枚ずつ用いて支払う。
- 3 円硬貨を 1 枚用いて支払う。
入力例 2
10 3 1 4 1 5 9 2 6 5 3
出力例 2
20
Score: 4 points
Problem Statement
You have coins of denominations 1, 2, \dots, N yen. For each denomination i, you have A_i coins.
Coins of the same denomination are indistinguishable.
Find the number of ways to pay exactly N yen using these coins, and output the result modulo 998244353.
Two payment methods are considered different if there exists at least one denomination for which the number of coins used differs.
Constraints
- 1 \leq N \leq 2.5 \times 10^5
- 1 \leq A_i \leq N
- All input values are integers
Input
The input is given from standard input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
3 1 2 3
Sample Output 1
2
There are 2 ways to pay exactly 3 yen:
- Use one 1-yen coin and one 2-yen coin.
- Use one 3-yen coin.
Sample Input 2
10 3 1 4 1 5 9 2 6 5 3
Sample Output 2
20