Problem Description

Once upon a time, there were two good friends named Xiao Yi and Xiao Huan. They were both famous sorting masters! For a permutation $p_1, p_2,\cdots, p_n$ of length $n$, Xiao Yi can, in one operation, choose an interval and cyclically shift it to the right by one position, while Xiao Huan can, in one operation, swap the positions of two different elements.

Here, a permutation $p_1, p_2,\cdots, p_n$ means a sequence satisfying $\{p_1, p_2,\cdots, p_n\}=\{1,2,\cdots,n\}$.

Formally,

• One operation of Xiao Yi: choose an interval $[l,r]$ ($1\le l\le r\le n$). If the elements in this interval are $p_l,p_{l+1},p_{l+2},\dots,p_r$, then after the operation they become $p_r,p_l,p_{l+1},p_{l+2}\dots,p_{r-1}$.
• One operation of Xiao Huan: choose two different positions $i,j$ ($1\le i<j\le n$), and swap $p_i$ and $p_j$.

Today, you planned to host a game of Shadow Kill, but Xiao Yi and Xiao Huan, who usually always join, did not come. You felt puzzled, so you decided to investigate. It turned out that a villain was trying to sow discord! First, he said to Xiao Yi: “Look at the permutation $[9,2,3,4,5,6,7,8,1]$. You actually need a whole $8$ operations to sort it! If Xiao Huan were here, he could finish it in one move. You are really not good at all—retire now!” Xiao Yi angrily drove him away, but that night this permutation kept haunting him, and he barely slept at all... Then the villain said to Xiao Huan: “Look at the permutation $[2,3,4,5,6,7,8,9,1]$. You actually need a whole $8$ operations to sort it! If Xiao Yi did it, he could finish it in one move. You are unbelievably bad—retire now!” Xiao Huan angrily chased him away, but that night this permutation kept spinning in his mind, and he had nightmares all night...

This is simply too absurd. Outsiders see more clearly than those involved, so you decide to clear up the misunderstanding in the most direct way: for a given integer $n$, for every $0\le i , j \le n-1$, you want to compute the number of permutations of length $n$, denoted $P_{i ,j}$, that satisfy: “when using a strategy that minimizes the number of operations, Xiao Yi needs exactly $i$ operations and Xiao Huan needs exactly $j$ operations to finish sorting.” Let the testdata speak—then they can fully understand each other’s ability, resolve the knot in their hearts, and become even better friends. Can you complete this task? Of course, since the number of permutations may be very large, given $mod$, please output the answers modulo $mod$.

Note that for two permutations of length $n$, $p_1,p_2,\cdots,p_n$ and $p'_1,p'_2,\cdots,p'_n$, they are considered different permutations and should be counted twice if and only if there exists an $i$ ($1\le i\le n$) such that $p_i\ne p'_i$.

Also note that “sorting” in the text above means sorting the permutation in increasing order, i.e. transforming a permutation $p_1,p_2,\cdots,p_n$ into $1,2,\cdots,n$ through operations.

Input Format

The input contains one line with two integers $n$ and $mod$ ($1\le n\le 150$, $2\le mod \le 10^9+7$), separated by a single space.

Output Format

Output $n$ lines, each containing $n$ integers separated by a single space. The $j$-th integer in the $i$-th line represents $P_{i-1,j-1} \bmod mod$.

3 21

1 0 0
0 2 1
0 1 1

10 10

1 0 0 0 0 0 0 0 0 0
0 9 8 7 6 5 4 3 2 1
0 8 7 9 1 0 3 7 9 6
0 7 9 3 1 0 2 4 8 6
0 6 1 1 4 7 8 4 6 6
0 5 0 0 7 6 7 3 8 9
0 4 3 2 8 7 4 3 5 4
0 3 7 4 4 3 3 6 6 4
0 2 9 8 6 8 5 6 8 4
0 1 6 6 6 9 4 4 4 0

15 2

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 1 0 1 1 1 0 1 1 1 0 1 1 1
0 0 0 1 0 1 1 0 1 0 0 1 0 1 1
0 1 1 0 0 1 1 0 1 1 1 0 0 1 1
0 0 1 1 1 0 0 1 0 1 0 0 0 1 1
0 1 1 1 1 0 0 1 0 0 0 0 0 1 1
0 0 0 0 0 1 1 0 1 0 0 0 0 1 1
0 1 1 1 1 0 0 1 1 0 0 0 0 1 1
0 0 1 0 1 1 0 0 0 0 1 0 1 1 0
0 1 1 0 1 0 0 0 0 1 1 0 1 0 0
0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0 0 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 1 1 1 0 0 0 0 0 0

Hint

Translated by ChatGPT 5