Recorder

AtCoder

IDfps_24_u

Time12000ms

Memory256MB

Difficulty—

We define the following as a **subproblem**: > There are $N$ programs numbered $1$ through $N$. Program $i$ is broadcast from time $A_i$ to time $B_i$. > You want to record all programs using $2$ recorders. > For a set of programs $S$, the condition that all programs in $S$ can be recorded by a single recorder is that no two programs in $S$ overlap in time. (It is acceptable if they only touch at the endpoints.) > > * More formally, all programs in $S$ can be recorded if there are no distinct $i, j \in S$ such that $\max(A_i, A_j) < \min(B_i, B_j)$ holds. > > The question is whether it is possible to record all programs using $2$ recorders. > More precisely, does there exist a partition $S_1, S_2$ of ${1, 2, \dots, N}$ such that both $S_1$ and $S_2$ can each be recorded by a single recorder? > Output `Yes` if it is possible, otherwise output `No`. > Constraints: > > * $0 \leq A_i < B_i \leq T$ > * $N, T, A_i, B_i$ are integers You are given $N$ and $U$. For each $T = 1, 2, \dots, U$, solve the following problem: * Suppose $N, T$ are the same as in the subproblem. Then, the number of possible inputs $(A_1, B_1), \dots, (A_N, B_N)$ is $\left(\dfrac{T(T+1)}{2}\right)^N$. Among them, count how many yield the answer `Yes` in the subproblem, and output the result modulo $998244353$. ## Constraints * $1 \leq N \leq 6 \times 10^4$ * $1 \leq U \leq 6 \times 10^4$ * $N, U$ are integers ## Input The input is given from standard input in the following format: $N$ $U$ ## Partial Score This problem has partial scoring: * If you solve all datasets with $N \leq 5 \times 10^3$ and $U \leq 5 \times 10^3$, you will earn $4$ points. [samples]

Samples

Input #1

3 4

Output #1

0
12
114
558

For example, when $T=2$, an input such as $(A_1, B_1) = (0, 2)$, $(A_2, B_2) = (0, 1)$, $(A_3, B_3) = (1, 2)$ satisfies the condition.

Input #2

7 10

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Recorder",
    "description": {
      "content": "We define the following as a **subproblem**: > There are $N$ programs numbered $1$ through $N$. Program $i$ is broadcast from time $A_i$ to time $B_i$.   > You want to record all programs using $2$ r",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 12000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "fps_24_u"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We define the following as a **subproblem**:\n\n> There are $N$ programs numbered $1$ through $N$. Program $i$ is broadcast from time $A_i$ to time $B_i$.  \n> You want to record all programs using $2$ r...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments