$n$ 次順列 $p$ の超過数を、$1 \le i \le n$ かつ $p_i > i$ を満たす $i$ の個数と定義し、降下数を、$1 \le i \le n-1$ かつ $p_i > p_{i+1}$ を満たす $i$ の個数と定義します。

$n$ 次順列の中で、超過数が $m$ であり、かつ降下数が $k$ である順列の個数を $h(n, m, k)$ とします。与えられた $n$ に対して、すべての $h(n, m, k)$ を計算してください。答えは非常に大きくなる可能性があるため、$M$ を法とした剰余を出力してください。

入力

1行に2つの正整数 $n$ と $M$ が与えられます。それぞれ順列の次数と法を表します。

出力

$n$ 行にわたって、各行に $n$ 個の数を出力してください。第 $i$ 行第 $j$ 列の数は $h(n, i-1, j-1) \bmod M$ とします。

入出力例

样例 1 入力

3 998244353

样例 1 出力

1 0 0
0 3 1
0 1 0

样例 1 注記

• 超過数が $0$、降下数が $0$ の順列：$[1, 2, 3]$。
• 超過数が $1$、降下数が $1$ の順列：$[2, 1, 3]$、$[3, 1, 2]$、$[1, 3, 2]$。
• 超過数が $1$、降下数が $2$ の順列：$[3, 2, 1]$。
• 超過数が $2$、降下数が $1$ の順列：$[2, 3, 1]$。

样例 2 入力

7 998244353

样例 2 出力

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

小課題

本問題はバンドルテスト方式を採用しています。

• $10\%$ のデータについて、$n \leq 10$ を満たす。
• $30\%$ のデータについて、$n \leq 20$ を満たす。
• $60\%$ のデータについて、$n \leq 35$ を満たす。
• $100\%$ のデータについて、$1 \le n \leq 60$、$M$ は素数、$10^8 \leq M \leq 10^9$ を満たす。

注記

剰余演算を高速化するために、以下のテンプレートを使用することができます。

#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;
}