在 Bytown，蕨类植物市场将在接下来的 $n$ 天内开放。第 $i$ 天蕨类植物的价格预先设定为 $a_i$ bytalars。每天，你可以决定以给定的价格买入或卖出一株蕨类植物，但（由于物流问题）你每天最多只能买入或卖出一株。你也可以选择在某一天什么都不做。当然，如果你手中没有蕨类植物，就不能卖出。不过，你可以储存无限数量的蕨类植物，并等待合适的时机卖出。你有充足的积蓄，不会因为蕨类植物投资而耗尽资金。你在第 1 天开始时没有任何蕨类植物，并且希望在第 $n$ 天市场关闭后手中也不持有任何蕨类植物。

定义 $f(a_1, a_2, \dots, a_n)$ 为如果你预先规划好买卖策略，通过交易蕨类植物所能获得的最大利润（以 bytalars 为单位）。对于任何自然数 $n$，令 $g(n)$ 为所有 $n!$ 种 $1$ 到 $n$ 的排列 $p$ 的 $f(p)$ 之和。

给定两个自然数 $k$ 和 $m$，其中 $m$ 是一个质数。输出 $g(1), g(2), \dots, g(k)$ 分别除以 $m$ 的余数。

输入格式

输入的第一行也是唯一一行包含两个整数 $k$ 和 $m$ ($1 \le k \le 7\,000$; $10^8 + 7 \le m \le 10^9 + 7$; $m$ 为质数)，如题目描述中所述。

输出格式

输出应包含 $k$ 行。第 $i$ 行应包含 $g(i)$ 除以 $m$ 的余数。

样例

输入 1

4 1000000007

输出 1

0
1
8
64

说明

如果 $n = 1$，市场只持续一天。由于你开始时没有蕨类植物，且希望结束时也没有蕨类植物，因此你无法进行任何交易。

如果 $n = 2$，有两种可能的价格序列：$[1, 2]$ 和 $[2, 1]$。在第一种情况下，你可以以 1 bytalar 的价格买入一株蕨类植物，然后以 2 bytalars 的价格卖出，获得 1 bytalar 的利润。因此，$f(1, 2) = 1$。在第二种情况下，你无法获得任何利润，即 $f(2, 1) = 0$。

对于 $n = 3$，有六种可能的价格序列： $f(1, 2, 3) = 2$, $f(1, 3, 2) = 2$, $f(2, 1, 3) = 2$, $f(2, 3, 1) = 1$, $f(3, 1, 2) = 1$, $f(3, 2, 1) = 0$.

在前三种情况下，你可以以 1 bytalar 的价格买入一株蕨类植物，然后以 3 bytalars 的价格卖出。在第四种情况下，你可以以 2 bytalars 的价格买入一株蕨类植物，并以 3 bytalars 的价格卖出。在第五种情况下，你可以以 1 bytalar 的价格买入一株蕨类植物，并以 2 bytalars 的价格卖出。在最后一种情况下，你无法获得任何利润。

注意，你可以储存多于一株的蕨类植物。例如，$f(2, 1, 4, 3) = 4$，因为你可以在第一天和第二天买入蕨类植物，然后在第三天和第四天卖出它们。