Given $n$, for each pair $x, y \in [0, n)$, find the number of permutations $p$ of $1 \sim n$ that 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$

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

The answer should be taken modulo the given prime $MOD$.

Input

A single line containing two integers $n$ and $MOD$.

Output

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

Constraints

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 additional constraints.

Examples

Input 1

3 1000000007

Output 1

1 0 0
0 4 0
0 0 1

Input 2

5 1000000007

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

Input 3

10 1000000007

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