给定 $ n $，对于每组 $ x,y\in [0,n) $ 求出有多少个 $ 1\sim n $ 的排列 $ p $ 满足以下条件：

• $ \sum\limits_{i=1}^{n-1}[p_i < p_{i+1}]=x $。
• $ \sum\limits_{i=1}^{n-1}[p^{-1}_i < p^{-1}_{i+1}]=y $。

其中 $ p^{-1} $ 表示 $ p $ 的逆排列，满足 $ p^{-1}_{p_i}=i $。

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

输入格式

共一行，两个整数，表示 $ n,MOD $。

输出格式

共 $ n $ 行，每行共 $ n $ 个整数，第 $ i $ 行第 $ j $ 列的数表示 $ x=i-1,y=j-1 $ 时的答案。

样例

样例输入 1

3 1000000007

样例输出 1

1 0 0
0 4 0
0 0 1

样例输入 2

5 1000000007

样例输出 2

1 0 0 0 0
0 20 6 0 0
0 6 54 6 0
0 0 6 20 0
0 0 0 0 1

样例输入 3

10 1000000007

样例输出 3

1 0 0 0 0 0 0 0 0 0
0 165 462 330 55 1 0 0 0 0
0 462 9273 22023 13750 2266 66 0 0 0
0 330 22023 147301 203610 75306 6556 66 0 0 
0 55 13750 203610 592130 423236 75306 2266 1 0
0 1 2266 75306 423236 592130 203610 13750 55 0
0 0 66 6556 75306 203610 147301 22023 330 0
0 0 0 66 2266 13750 22023 9273 462 0
0 0 0 0 1 55 330 462 165 0
0 0 0 0 0 0 0 0 0 1

数据范围

对于 $ 100\% $ 数据，$ 1\le n\le 500,10^9\le MOD\le 1.01\times 10^9 $，保证 $ MOD $ 为质数。

$ \operatorname{Subtask} 1(10\%):n\le 8 $。

$ \operatorname{Subtask} 2(15\%):n\le 16 $。

$ \operatorname{Subtask} 3(25\%):n\le 40 $。

$ \operatorname{Subtask} 4(25\%):n\le 100 $。

$ \operatorname{Subtask} 5(25\%): $ 无特殊限制。