Ορίζουμε ως υπέρβαση (exceedance) μιας μετάθεσης $p$ τάξης $n$ το πλήθος των δεικτών $i$ τέτοιων ώστε $1 \le i \le n$ και $p_i > i$, και ως πτώση (descent) το πλήθος των δεικτών $i$ τέτοιων ώστε $1 \le i \le n-1$ και $p_i > p_{i+1}$.

Έστω $h(n, m, k)$ το πλήθος των μεταθέσεων τάξης $n$ που έχουν $m$ υπερβάσεις και $k$ πτώσεις. Για ένα δεδομένο $n$, υπολογίστε όλες τις τιμές $h(n, m, k)$. Επειδή οι απαντήσεις είναι μεγάλες, αρκεί να εκτυπώσετε τις τιμές τους modulo $M$.

Μορφή Εισόδου

Μία γραμμή που περιέχει δύο θετικούς ακέραιους $n$ και $M$, που αντιπροσωπεύουν την τάξη της μετάθεσης και τον μέτρο (modulus).

Μορφή Εξόδου

Εκτυπώστε $n$ γραμμές, καθεμία από τις οποίες περιέχει $n$ αριθμούς. Ο $j$-οστός αριθμός της $i$-οστής γραμμής πρέπει να είναι η τιμή $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

Υποπροβλήματα

Το πρόβλημα χρησιμοποιεί ομαδοποιημένη βαθμολόγηση (bundled testing).

Για το $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$.

Σημείωση

Μπορείτε να χρησιμοποιήσετε το παρακάτω πρότυπο για να επιταχύνετε τις πράξεις 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;
}