God: “Concise problems touch the essence.”

God: “Complexity is not profundity, and chaos is not freedom.”

God: “Strip away contingency, and what remains is inevitability.”

God: “$\exp(O(n))$ is a hypocritical victory, while $\text{poly}(n)$ is an eternal truth.”

This is the last oracle received by a former competitive programmer. After careful polishing by him and his friends, it finally became this gift presented to everyone.

Formal statement:

Given $n$, arrange all sets $S$ satisfying $S\subseteq [n],\ 1\le |S|\le 2$ into a sequence, such that ${x,y}$ is between ${x}$ and ${y}$, and ${x}$ is before ${x+1}$.

For every pair $1\le i\le n,\ 1\le j\le n(n+1)/2$, compute the number of valid sequences in which the index (position) of ${i}$ is $j$. Output the answer modulo a given prime $p$.

Input Format

A single line containing two integers $n,p$.

Output Format

Output $n$ lines, each containing $n(n+1)/2$ integers. The $j$-th number on the $i$-th line denotes the number of valid sequences in which the index of ${i}$ is $j$.

Example 1

input

1 851214401

output

1

Example 2

input

3 922820713

output

4 0 0 0 0 0
0 0 2 2 0 0
0 0 0 0 0 4

Example 3

input

4 682679827

output

144 0 0 0 0 0 0 0 0 0
0 0 60 60 24 0 0 0 0 0
0 0 0 0 0 24 60 60 0 0
0 0 0 0 0 0 0 0 0 144

Example 4 $\sim$ Example 10

See the attached files.

Constraints

For $100%$ of the data: $1\le n\le 40,\ 10^8< p< 10^9$. It is guaranteed that $p$ is prime.

We provide a $\text{Barrett}$ modular multiplication template to speed up modulo operations:

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b; // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
};
FastMod F(2);

int main() {
    int M = 1000000007; F = FastMod(M);
    ull x = 10ULL*M+3; 
    cout <<; x << " " << F.reduce(x) << "\n"; // 10000000073 3
}