Coin 2

AtCoder

IDfps_24_n

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

3
1 2 3

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.

Input #2

10
3 1 4 1 5 9 2 6 5 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Coin 2",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "fps_24_n"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have coins of denominations $1, 2, \\dots, N$ yen. For each denomination $i$, you have $A_i$ coins.  \nCoins of the same denomination are indistinguishable.\nFind the number of ways to pay exactly $N...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments