最近，Bytecja 开始对一个新发现的大陆及其无数周边岛屿进行殖民。不幸的是，当地原住民对殖民者的到来并不欢迎。

岛上的殖民过程如下：岛上有 $n$ 个村庄，通过 $n-1$ 条双向道路连接，使得从任何一个村庄都可以到达其他任何村庄。换句话说，每个岛上的村庄和道路布局构成了一棵树。最初，在殖民者选择的一个村庄中，出现了 $k$ 个殖民者，使得该村庄被殖民。此后，殖民者可以沿着道路自由移动，或等待其他殖民者的移动。当殖民者到达一个村庄时，该村庄即被殖民。

占领整个岛屿即使只有一个殖民者也很简单，但有一个问题——如果一个已殖民的村庄在没有等待的殖民者的情况下，且与一个未殖民的村庄相邻，当地人可能会袭击它，导致悲惨的后果。因此，必须避免这种情况。殖民者必须守卫这样的村庄，或者待在这些村庄之间的道路上，因为当地人绝对不会绕过他。

对于给定的设置，问题是使整个岛屿能够被殖民的最小 $k$ 值，以及殖民者初始村庄的选择和移动策略。

你的任务是：给定数字 $n$，对于每个 $k$，确定岛上需要恰好 $k$ 个殖民者才能被征服的可能的道路布局数量。如果两个树不同构，则认为它们的道路布局不同（即你需要计算无标号树）。换句话说，如果两个布局之间不存在双射，使得第一个布局中的两个村庄通过道路连接当且仅当它们在第二个布局中的对应村庄通过道路连接，则这两个道路布局是不同的。

由于这些数字可能非常大，你可以提供这些数字对给定素数的模。

输入格式

输入的第一行包含两个整数 $n$ 和 $p$ ($2 \le n \le 500$; $10^8 + 7 \le p \le 10^9 + 7$; $p$ 是一个素数)，分别代表岛上的村庄数量和提到的素数。

输出格式

输出的第一行应包含 $n$ 个整数。第 $k$ 个数字应表示在 $n$ 个村庄中，需要恰好 $k$ 个殖民者才能被征服的、不同的道路布局数量，结果对 $p$ 取模。

样例

样例输入 1

3 100000007

样例输出 1

1 0 0

样例输入 2

6 300000007

样例输出 2

1 5 0 0 0 0

样例输入 3

10 1000000007

样例输出 3

1 104 1 0 0 0 0 0 0 0

说明

在第一个样例测试中，只有一种可能的道路布局，如下所示：

要殖民这样的岛屿，只需要一个殖民者，前提是他不从中心村庄开始。

在第二个样例测试中，有 6 种可能的道路布局，如下所示：

这些布局中只有左上角的布局可以在仅有一个殖民者的情况下被殖民。对于所有其他布局，都需要恰好两个殖民者。例如，在中间右侧的布局中，他们可以从最左侧的村庄开始，一起向右移动两个村庄，然后其中一个等待另一个，后者随后依次殖民剩余的三个村庄。

在第三个样例测试中，只有一个布局需要三个殖民者，如下所示：