On appelle nombre d'excédances d'une permutation $p$ d'ordre $n$ le nombre d'indices $i$ tels que $1 \le i \le n$ et $p_i > i$, et nombre de descentes le nombre d'indices $i$ tels que $1 \le i \le n-1$ et $p_i > p_{i+1}$.

Soit $h(n, m, k)$ le nombre de permutations d'ordre $n$ ayant $m$ excédances et $k$ descentes. Pour un $n$ donné, calculez toutes les valeurs de $h(n, m, k)$. Comme les résultats peuvent être très grands, vous ne devez afficher que leurs valeurs modulo $M$.

Entrée

Une ligne contenant deux entiers positifs $n$ et $M$, représentant l'ordre de la permutation et le module.

Sortie

Affichez $n$ lignes, chacune contenant $n$ nombres, où le $j$-ième nombre de la $i$-ième ligne correspond à $h(n, i-1, j-1) \bmod M$.

Exemples

Exemples 1

Entrée :

3 998244353

Sortie :

1 0 0
0 3 1
0 1 0

Remarque

• Permutations avec 0 excédance et 0 descente : $[1, 2, 3]$.
• Permutations avec 1 excédance et 1 descente : $[2, 1, 3]$, $[3, 1, 2]$, $[1, 3, 2]$.
• Permutations avec 1 excédance et 2 descentes : $[3, 2, 1]$.
• Permutations avec 2 excédances et 1 descente : $[2, 3, 1]$.

Exemples 2

Entrée :

7 998244353

Sortie :

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

Sous-tâches

Ce problème utilise des tests groupés.

Pour $10\%$ des données, $n \leq 10$.

Pour $30\%$ des données, $n \leq 20$.

Pour $60\%$ des données, $n \leq 35$.

Pour $100\%$ des données, $1 \le n \leq 60$, $M$ est un nombre premier, $10^8 \leq M \leq 10^9$.

Remarque

Vous pouvez choisir d'utiliser le modèle suivant pour accélérer les opérations 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;
}