ZigZag Break

AtCoder

IDagc054_e

Time2000ms

Memory256MB

Difficulty—

Given are integers $N$ and $A$. Find the number, modulo $998244353$, of permutations $P=(P_1,P_2,\cdots,P_N)$ of $(1,2,\cdots,N)$ that satisfy the following conditions. * $P_1=A$. * It is possible to repeat the following operation so that $P$ has just two elements. * Choose three **consecutive** elements $x$, $y$, and $z$. Here, $y<\min(x,z)$ or $y>\max(x,z)$ must hold. Then, erase $y$ from $P$. Solve $T$ test cases in an input file. ## Constraints * $1 \leq T \leq 5 \times 10^5$ * $3 \leq N \leq 10^6$ * $1 \leq A \leq N$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $T$ $case_1$ $case_2$ $\vdots$ $case_T$ Each case is in the following format: $N$ $A$ [samples]

Samples

Input #1

8
3 1
3 2
3 3
4 1
4 2
4 3
4 4
200000 10000

Output #1

1
2
1
3
5
5
3
621235018

When $N=4,A=2$, one permutation that satisfies the condition is $P=(2,1,4,3)$. One way to make it have just two elements is as follows.

*   Choose $(x,y,z)=(2,1,4)$ to erase $1$, resulting in $P=(2,4,3)$.
*   Choose $(x,y,z)=(2,4,3)$ to erase $4$, resulting in $P=(2,3)$.

API Response (JSON)

{
  "problem": {
    "name": "ZigZag Break",
    "description": {
      "content": "Given are integers $N$ and $A$. Find the number, modulo $998244353$, of permutations $P=(P_1,P_2,\\cdots,P_N)$ of $(1,2,\\cdots,N)$ that satisfy the following conditions. *   $P_1=A$. *   It is possibl",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc054_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given are integers $N$ and $A$. Find the number, modulo $998244353$, of permutations $P=(P_1,P_2,\\cdots,P_N)$ of $(1,2,\\cdots,N)$ that satisfy the following conditions.\n\n*   $P_1=A$.\n*   It is possibl...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments