{"problem":{"name":"Keep Connect","description":{"content":"You are given an integer $N$ greater than or equal to $2$ and a prime $P$.   Consider the graph $G$ with $2N$ vertices and $(3N-2)$ edges shown in the figure below. ![image](https://img.atcoder.jp/ab","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc248_f"},"statements":[{"statement_type":"Markdown","content":"You are given an integer $N$ greater than or equal to $2$ and a prime $P$.  \nConsider the graph $G$ with $2N$ vertices and $(3N-2)$ edges shown in the figure below.\n\n![image](https://img.atcoder.jp/abc248/2f39ecad6f55c6f9a5eb27d048b3020e.png)\n\nMore specifically, the edges connect the vertices as follows, where the vertices are labeled as Vertex $1$, Vertex $2$, $\\ldots$, Vertex $2N$, and the edges are labeled as Edge $1$, Edge $2$, $\\ldots$, Edge $(3N-2)$.\n\n*   For each $1\\leq i\\leq N-1$, Edge $i$ connects Vertex $i$ and Vertex $i+1$.\n*   For each $1\\leq i\\leq N-1$, Edge $(N-1+i)$ connects Vertex $N+i$ and Vertex $N+i+1$.\n*   For each $1\\leq i\\leq N$, Edge $(2N-2+i)$ connects Vertex $i$ and Vertex $N+i$.\n\nFor each $i=1,2,\\ldots ,N-1$, solve the following problem.\n\n> Find the number of ways, modulo $P$, to remove exactly $i$ of the $3N-2$ edges of $G$ so that the resulting graph is still connected.\n\n## Constraints\n\n*   $2 \\leq N \\leq 3000$\n*   $9\\times 10^8 \\leq P \\leq 10^9$\n*   $N$ is an integer.\n*   $P$ is a prime.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $P$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc248_f","tags":[],"sample_group":[["3 998244353","7 15\n\nIn the case $N=3$, there are $7$ ways, shown below, to remove exactly one edge so that the resulting graph is still connected.\n![image](https://img.atcoder.jp/abc248/57f65600b77ee654900cff4ea6e40872.png)\nThere are $15$ ways, shown below, to remove exactly two edges so that the resulting graph is still connected.\n![image](https://img.atcoder.jp/abc248/3a7d6523a1252886e9a33204a32e45f5.png)\nThus, these numbers modulo $P=998244353$ should be printed: $7$ and $15$, in this order."],["16 999999937","46 1016 14288 143044 1079816 6349672 29622112 110569766 330377828 784245480 453609503 38603306 44981526 314279703 408855776\n\nBe sure to print the numbers modulo $P$."]],"created_at":"2026-03-03 11:01:13"}}