{"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$ recorders.\n> 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.)\n> \n> *   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.\n> \n> The question is whether it is possible to record all programs using $2$ recorders.  \n> 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?  \n> Output `Yes` if it is possible, otherwise output `No`.\n> Constraints:\n> \n> *   $0 \\leq A_i < B_i \\leq T$\n> *   $N, T, A_i, B_i$ are integers\n\nYou are given $N$ and $U$.  \nFor each $T = 1, 2, \\dots, U$, solve the following problem:\n\n*   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$.  \n    Among them, count how many yield the answer `Yes` in the subproblem, and output the result modulo $998244353$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 6 \\times 10^4$\n*   $1 \\leq U \\leq 6 \\times 10^4$\n*   $N, U$ are integers\n\n## Input\n\nThe input is given from standard input in the following format:\n\n$N$ $U$\n\n## Partial Score\n\nThis problem has partial scoring:\n\n*   If you solve all datasets with $N \\leq 5 \\times 10^3$ and $U \\leq 5 \\times 10^3$, you will earn $4$ points.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"fps_24_u","tags":[],"sample_group":[["3 4","0\n12\n114\n558\n\nFor 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."],["7 10","0\n0\n0\n6300\n260820\n4161780\n39414060\n265208580\n398083867\n112841142"]],"created_at":"2026-03-03 11:01:14"}}