Llamamos excedencia de una permutación $p$ de orden $n$ a la cantidad de índices $i$ tales que $1 \le i \le n$ y $p_i > i$, y descenso a la cantidad de índices $i$ tales que $1 \le i \le n-1$ y $p_i > p_{i+1}$.

Sea $h(n, m, k)$ la cantidad de permutaciones de orden $n$ que tienen $m$ excedencias y $k$ descensos. Para un $n$ dado, calcula todos los valores de $h(n, m, k)$. Dado que las respuestas pueden ser muy grandes, solo necesitas imprimir sus valores módulo $M$.

Entrada

Una línea con dos enteros positivos $n$ y $M$, que representan el orden de la permutación y el módulo, respectivamente.

Salida

Imprime $n$ líneas, cada una con $n$ números; el $j$-ésimo número de la $i$-ésima línea debe ser $h(n, i-1, j-1) \bmod M$.

Ejemplos

Ejemplo 1 Entrada

3 998244353

Ejemplo 1 Salida

1 0 0
0 3 1
0 1 0

Ejemplo 1 Nota

• Permutaciones con $0$ excedencias y $0$ descensos: $[1, 2, 3]$.
• Permutaciones con $1$ excedencia y $1$ descenso: $[2, 1, 3]$, $[3, 1, 2]$, $[1, 3, 2]$.
• Permutaciones con $1$ excedencia y $2$ descensos: $[3, 2, 1]$.
• Permutaciones con $2$ excedencias y $1$ descenso: $[2, 3, 1]$.

Ejemplo 2 Entrada

7 998244353

Ejemplo 2 Salida

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

Subtareas

Este problema utiliza pruebas por lotes (bundled testing).

Para el $10\%$ de los datos, se garantiza que $n \leq 10$.

Para el $30\%$ de los datos, se garantiza que $n \leq 20$.

Para el $60\%$ de los datos, se garantiza que $n \leq 35$.

Para el $100\%$ de los datos, se garantiza que $1 \le n \leq 60$, $M$ es un número primo y $10^8 \leq M \leq 10^9$.

Nota

Puedes optar por utilizar la siguiente plantilla para acelerar las operaciones de módulo.

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