{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $P$"},{"iden":"sample input 1","content":"3 998244353"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"16 999999937"},{"iden":"sample output 2","content":"46 1016 14288 143044 1079816 6349672 29622112 110569766 330377828 784245480 453609503 38603306 44981526 314279703 408855776\n\nBe sure to print the numbers modulo $P$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}