Background

A junior student asks you for help with the following problem:

• Given a rooted tree with $n$ nodes, all nodes are initially white.
• You can perform at most $k$ operations. In each operation, you select a node and paint all nodes on the simple path from that node to the root black.
• Find the maximum number of nodes you can paint black. Solve this for each $k = 1 \sim n$.

This is certainly not a difficult problem. You explain the solution to the student, who marvels at the ingenuity of the approach and leaves satisfied.

Watching them walk away, you recall that two or three years ago, when you first learned how to solve this problem, you also marveled at its solution. But for you now, there is nothing magical about it; it is just a common routine.

However, well-known problems and conclusions are not necessarily boring or uninteresting. Thinking this, you record the problem:

Description

• Given a rooted tree with $n$ nodes, all nodes are initially white.
• You can perform at most $k$ operations. In each operation, you select a node and paint all nodes on the simple path from that node to the root black.
• Find the maximum number of nodes you can paint black. Solve this for each $k = 1 \sim n$.

Let $ans(T, i)$ be the answer to the above problem for a labeled rooted tree $T$ when $k = i$.

Given $n$ and $\text{mod}$, for all $1 \le k \le n$ and $1 \le m \le n$, calculate how many different labeled rooted trees $T$ with $n$ nodes (rooted at $1$) satisfy $ans(T, k) = m$. The answer should be modulo $\text{mod}$.

Two labeled trees rooted at $1$ are considered different if and only if their edge sets are different.

Input

A single line containing two integers $n$ and $\text{mod}$.

Output

Output $n$ lines, each containing $n$ integers. The $m$-th integer in the $k$-th line represents the number of different labeled rooted trees $T$ with $n$ nodes (rooted at $1$) such that $ans(T, k) = m$, modulo $\text{mod}$.

Examples

Input 1

2 998244353

Output 1

0 1 
0 1

Input 2

3 998244353

Output 2

0 1 2 
0 0 3 
0 0 3

Input 3

4 998244353

Output 3

0 1 9 6 
0 0 1 15 
0 0 0 16 
0 0 0 16

Input 4

5 998244353

Output 4

0 1 40 60 24 
0 0 1 28 96 
0 0 0 1 124 
0 0 0 0 125 
0 0 0 0 125

Input 5

6 998244353

Output 5

0 1 195 560 420 120 
0 0 1 75 500 720 
0 0 0 1 75 1220 
0 0 0 0 1 1295 
0 0 0 0 0 1296 
0 0 0 0 0 1296

Constraints

This problem uses bundled testing. You must pass all test cases in a subtask to receive points for that subtask.

For all data: $1 \le n \le 300$, $10^8 \le \text{mod} \le 1.05 \times 10^9$, and $\text{mod}$ is guaranteed to be a prime number.