Background

Problem Description

Given $n$, for each pair $x \in [0, n)$ and $y \in [1, 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$.
• There are exactly $y$ permutation cycles in $p$.

Take the answer modulo the given prime $P$.

Input Format

One line with two positive integers $n, P$.

Output Format

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

3 1000000007

0 1 0
2 2 0
0 0 1

5 1000000007

0 0 1 0 0
6 12 8 0 0
12 30 18 6 0
6 8 8 4 0
0 0 0 0 1

10 1000000007

0 0 0 0 1 0 0 0 0 0
105 286 341 195 71 15 0 0 0 0
4773 14122 16301 9444 2819 381 0 0 0 0
45525 132768 153353 90556 28471 4299 220 0 0 0
131049 375730 431900 261660 90786 17649 1580 0 0 0
131019 367570 418355 261804 101865 25710 3800 231 0 0
45519 123618 138737 90477 40295 13061 3072 413 0 0
4791 12256 13479 9353 4901 2081 740 203 36 0
99 226 234 191 116 77 38 23 9 0
0 0 0 0 0 0 0 0 0 1

Hint

Constraints: For all testdata, $1 \le n \le 200$, $9.9 \times 10^8 \le P \le 1.01 \times 10^9$, and $P$ is guaranteed to be prime.

Click here to view another version of this problem。

Translated by ChatGPT 5