题目描述

给定一个长度为 $n$ 的排列 $[1,2,\ldots,n]$，你可以进行以下操作：

选择一个数，将其取出然后放到排列的开头或末尾。

对每个 $k=0,1,\ldots,n-1$，求出进行至多 $k$ 次操作可能得到的排列个数。由于这些数可能非常大，你只需要回答它们除以 $m$ 的余数即可。

输入格式

一行两个整数 $n,m$（$1\le n\le 1000$，$10^8\le m\le 10^9+9$，$m$ 是素数）。

输出格式

$n$ 行，第 $i$ 行一个整数表示 $k=i-1$ 时的答案。

样例 1

• 输入： $3$ $998244353$
• 输出： $1$ $5$ $6$

说明：$n=3$ 时，进行至多 $1$ 次操作可以得到除 $[3,2,1]$ 外的所有排列。

样例 2

• 输入： $1$ $100000007$
• 输出： $1$

样例 3

• 输入： $20$ $1000000009$
• 输出： $1$ $39$ $1100$ $26220$ $554040$ $10581480$ $184187520$ $930255982$ $586386822$ $781249333$ $374807160$ $139825602$ $462558935$ $67876942$ $578348054$ $201415654$ $108018732$ $350356788$ $280522125$ $280522126$

数据范围与提示

• Subtask #1 (10 points): $n\le 10$。
• Subtask #2 (10 points): $n\le 18$。
• Subtask #3 (10 points): $n\le 50$。
• Subtask #4 (30 points): $n\le 300$。
• Subtask #5 (40 points): 无额外限制。