Problem Description

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

• \(\sum_{i=1}^{n-1}[p_i < p_{i+1}] = x\).

• \(\sum_{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 \).

The answer should be taken modulo a given prime number \( MOD \).

Input Format

A single line containing two integers, \( n \) and \( MOD \).

Output Format

A total of \( n \) lines, each containing \( n \) integers. The integer at the \( i \)-th row and \( j \)-th column represents the answer when \( x = i-1 \) and \( y = j-1 \).

Sample Input and Output

Sample Input #1

3 1000000007

Sample Output #1

1 0 0
0 4 0
0 0 1

Sample Input #2

5 1000000007

Sample Output #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

Sample Input #3

10 1000000007

Sample Output #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

Notes

For \( 100\% \) of the data, \( 1 \le n \le 500 \), \( 10^9 \le MOD \le 1.01 \times 10^9 \), and \( MOD \) is guaranteed to be a prime number.

• Subtask 1 (10%): \( n \le 8 \).
• Subtask 2 (15%): \( n \le 16 \).
• Subtask 3 (25%): \( n \le 40 \).
• Subtask 4 (25%): \( n \le 100 \).
• Subtask 5 (25%): No special restrictions.

见题面 Input 部分

见题面 Output 部分