Growth Rate

AtCoder

IDarc118_f

Time4000ms

Memory256MB

Difficulty—

Given is a positive integer $M$ and a sequence of $N$ integers: $A = (A_1,A_2,\ldots,A_N)$. Find the number, modulo $998244353$, of sequences of $N+1$ integers, $X = (X_1,X_2, \ldots, X_{N+1})$, satisfying all of the following conditions: * $1\leq X_i\leq M$ ($1\leq i\leq N+1$) * $A_iX_i\leq X_{i+1}$ ($1\leq i\leq N$) ## Constraints * $1\leq N\leq 1000$ * $1\leq M\leq 10^{18}$ * $1\leq A_i\leq 10^9$ * $\prod_{i=1}^N A_i \leq M$ ## Input Input is given from Standard Input in the following format: $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ [samples]

Samples

Input #1

2 10
2 3

Output #1

7

Seven sequences below satisfy the conditions.

*   $(1, 2, 6)$, $(1,2,7)$, $(1,2,8)$, $(1,2,9)$, $(1,2,10)$, $(1,3,9)$, $(1,3,10)$

Input #2

2 10
3 2

Output #2

9

Nine sequences below satisfy the conditions.

*   $(1, 3, 6)$, $(1, 3, 7)$, $(1, 3, 8)$, $(1, 3, 9)$, $(1, 3, 10)$, $(1, 4, 8)$, $(1, 4, 9)$, $(1, 4, 10)$, $(1, 5, 10)$

Input #3

7 1000
1 2 3 4 3 2 1

Output #3

225650129

Input #4

5 1000000000000000000
1 1 1 1 1

Output #4

307835847

API Response (JSON)

{
  "problem": {
    "name": "Growth Rate",
    "description": {
      "content": "Given is a positive integer $M$ and a sequence of $N$ integers: $A = (A_1,A_2,\\ldots,A_N)$. Find the number, modulo $998244353$, of sequences of $N+1$ integers, $X = (X_1,X_2, \\ldots, X_{N+1})$, satis",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc118_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given is a positive integer $M$ and a sequence of $N$ integers: $A = (A_1,A_2,\\ldots,A_N)$. Find the number, modulo $998244353$, of sequences of $N+1$ integers, $X = (X_1,X_2, \\ldots, X_{N+1})$, satis...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments