Za permutaciju $p$ reda $n$, broj prekoračenja definiramo kao broj indeksa $i$ takvih da je $1 \le i \le n$ i $p_i > i$, a broj padova kao broj indeksa $i$ takvih da je $1 \le i \le n-1$ i $p_i > p_{i+1}$.

Neka je $h(n, m, k)$ broj permutacija reda $n$ koje imaju točno $m$ prekoračenja i $k$ padova. Za zadani $n$, izračunajte sve vrijednosti $h(n, m, k)$. Budući da su rezultati veliki, potrebno je ispisati njihove vrijednosti po modulu $M$.

Ulazni format

U jednom retku nalaze se dva pozitivna cijela broja $n$ i $M$, koji predstavljaju red permutacije i modul.

Izlazni format

Ispišite $n$ redaka, svaki s $n$ brojeva, gdje $j$-ti broj u $i$-tom retku predstavlja $h(n, i-1, j-1) \bmod M$.

Primjeri podataka

Primjer 1 Ulaz

3 998244353

Primjer 1 Izlaz

1 0 0
0 3 1
0 1 0

Primjer 1 Objašnjenje

• Permutacije s $0$ prekoračenja i $0$ padova: $[1, 2, 3]$.
• Permutacije s $1$ prekoračenjem i $1$ padom: $[2, 1, 3]$, $[3, 1, 2]$, $[1, 3, 2]$.
• Permutacije s $1$ prekoračenjem i $2$ pada: $[3, 2, 1]$.
• Permutacije s $2$ prekoračenja i $1$ padom: $[2, 3, 1]$.

Primjer 2 Ulaz

7 998244353

Primjer 2 Izlaz

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

Podzadaci

Zadatak koristi grupno testiranje.

Za $10\%$ podataka vrijedi $n \leq 10$.

Za $30\%$ podataka vrijedi $n \leq 20$.

Za $60\%$ podataka vrijedi $n \leq 35$.

Za $100\%$ podataka vrijedi $1 \le n \leq 60$, $M$ je prost broj, $10^8 \leq M \leq 10^9$.

Napomena

Možete koristiti sljedeći predložak za ubrzanje operacije modulo.

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