Sirius II

给定 $n$，将所有满足 $1\le x,y\le n$ 的二元组 $(x,y)$ 排成一列，要求 $(x,y)$ 在 $(x,x)$ 与 $(y,y)$ 之间，且 $(x,x)$ 在 $(x+1,x+1)$ 之前。

对于每一对 $1\le i\le n,1\le j\le n^2$ 求出 $(i,i)$ 的下标为 $j$ 的方案数。

答案对给定的质数 $p$ 取模。

输入格式

一行，两个整数 $n,p$。

输出格式

共 $n$ 行，每行 $n^2$ 个整数。第 $i$ 行的第 $j$ 个数表示 $(i,i)$ 下标为 $j$ 的方案数。

提示

对于 $100\%$ 的数据，$1\le n\le 40,10^8< p< 10^9$，保证 $p$ 为质数。

$\text{Subtask }1(5\%):n\le 5$。

$\text{Subtask }2(5\%):n\le 10$。

$\text{Subtask }3(10\%):n\le 15$。

$\text{Subtask }4(10\%):n\le 20$。

$\text{Subtask }5(15\%):n\le 25$。

$\text{Subtask }6(15\%):n\le 30$。

$\text{Subtask }7(20\%):n\le 35$。

$\text{Subtask }8(20\%):n\le 40$。