有 $n$ 个人要把外套挂到行李寄存处的 $n+2$ 个衣服钩子上。这些钩子从左往右等距排成一排，最左和最右两个钩子上挂着管事的人的衣服，这是不能动的。这些人要挂在剩下 $n$ 个钩子上。我们把这中间 $n$ 个钩子按左往右的顺序从 $1$ 到 $n$ 编号。

现在 $n$ 个人依次把衣服挂上去，我们将这些人按先后顺序从 $1$ 到 $n$ 编号。每个人都不喜欢和别人贴在一起，所以当一个人挂衣服时，他会计算每个空钩子 $x$ 和已经挂了衣服钩子的最短距离 $d_x$，以及 $d = \max\{d_x\}$，之后他会在所有满足 $d_x=d$ 的衣服钩子 $x$ 中等概率随机挑选一个挂上衣服。

给定 $n$ 和质数 $P$，我们希望你对于 $1 \le i,j \le n$ 都计算出，$i$ 号人把衣服挂在 $j$ 号钩子上的概率，对 $P$ 取模的结果。

数据保证答案概率可以表示成既约分数 $x/y$，且 $y$ 不是 $P$ 的倍数，那么你只需输出 $x \times y^{P-2} \bmod P$.

输入格式

仅一行两个整数 $n$ 和 $P$.

输出格式

输出 $n$ 行，每行 $n$ 个数，第 $i$ 行的第 $j$ 个数表示 $i$ 号人把衣服挂在 $j$ 号钩子上的概率，对 $P$ 取模的结果。

输入输出中相邻两个整数用空格隔开。

样例 1 输入

3 1000000007

样例 1 输出

0 1 0
500000004 0 500000004
500000004 0 500000004

样例 2 输入

4 1000000007

样例 2 输出

0 500000004 500000004 0
333333336 166666668 166666668 333333336
333333336 166666668 166666668 333333336
333333336 166666668 166666668 333333336

子任务

对于所有数据，保证 $1 \le n \le 1000,10^9<P<1.1 \times 10^9$ 且 $P$ 是质数。

1. $n \le 20$（10 分）
2. $n \le 30$（10 分）
3. $n \le 50$（25 分）
4. $n \le 100$（20 分）
5. $n \le 300$（15 分）
6. 没有特殊限制（20 分）

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$