We define the excedance number of a permutation $p$ of order $n$ as the number of indices $i$ such that $1 \le i \le n$ and $p_i > i$, and the descent number as the number of indices $i$ such that $1 \le i \le n-1$ and $p_i > p_{i+1}$.

Let $h(n, m, k)$ be the number of permutations of order $n$ with an excedance number of $m$ and a descent number of $k$. For a given $n$, calculate all $h(n, m, k)$. Since the answers can be very large, you only need to output their values modulo $M$.

Input

A single line containing two positive integers $n$ and $M$, representing the order of the permutation and the modulus.

Output

Output $n$ lines, each containing $n$ numbers. The $j$-th number in the $i$-th line should be $h(n, i-1, j-1) \bmod M$.

Examples

Examples 1 Input

3 998244353

Examples 1 Output

1 0 0
0 3 1
0 1 0

Examples 1 Note

• Permutations with excedance number $0$ and descent number $0$: $[1, 2, 3]$.
• Permutations with excedance number $1$ and descent number $1$: $[2, 1, 3]$, $[3, 1, 2]$, $[1, 3, 2]$.
• Permutations with excedance number $1$ and descent number $2$: $[3, 2, 1]$.
• Permutations with excedance number $2$ and descent number $1$: $[2, 3, 1]$.

Examples 2 Input

7 998244353

Examples 2 Output

1 0 0 0 0 0 0
0 21 70 28 1 0 0
0 35 343 596 209 8 0
0 35 470 1154 673 83 1
0 21 259 582 300 29 0
0 7 49 56 8 0 0
0 1 0 0 0 0 0

Subtasks

This problem uses bundled testing.

For $10\%$ of the data, $n \leq 10$.

For $30\%$ of the data, $n \leq 20$.

For $60\%$ of the data, $n \leq 35$.

For $100\%$ of the data, $1 \le n \leq 60$, $M$ is a prime number, $10^8 \leq M \leq 10^9$.

Note

You may choose to use the following template to speed up modular arithmetic.

#include <bits/stdc++.h>

using namespace std;

using u64 = unsigned long long;
using LL = __uint128_t;

struct FastMod {
    u64 b, m;

    FastMod(u64 b) : b(b), m(u64((LL(1) << 64) / b)) {}

    u64 operator()(u64 a) {
        u64 q = (u64) ((LL(m) * a) >> 64);
        u64 r = a - q * b;
        return r >= b ? r - b : r;
    }
} R(2);

int mod;

int main() {
    int n; cin >> n >> mod; R = FastMod(mod);

    int a = 1e7, b = 2e7;
    int c = R(a * (u64)b);

    return 0;
}