Problem Description

Given $n$, for each pair $x,y\in [0,n)$, find how many permutations $p$ of $1\sim n$ satisfy the following conditions:

• $\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$.

Here $p^{-1}$ denotes the inverse permutation of $p$, satisfying $p^{-1}_{p_i}=i$.

Output the answer modulo the given prime $MOD$.

Input Format

One line with two integers, $n,MOD$.

Output Format

Output $n$ lines, each containing $n$ integers. The number in row $i$ and column $j$ denotes the answer when $x=i-1,y=j-1$.

3 1000000007

1 0 0
0 4 0
0 0 1

5 1000000007

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

10 1000000007

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

Hint

For $100\%$ of the testdata, $1\le n\le 500$, $10^9\le MOD\le 1.01\times 10^9$, and $MOD$ is guaranteed to be prime.

$\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\%):$ No special constraints.

Translated by ChatGPT 5