نُسمي عدد التجاوزات لتبديلة $p$ من الرتبة $n$ بأنه عدد قيم $i$ التي تحقق $1 \le i \le n$ و $p_i > i$، ونُسمي عدد الانخفاضات بأنه عدد قيم $i$ التي تحقق $1 \le i \le n-1$ و $p_i > p_{i+1}$.

ليكن $h(n, m, k)$ هو عدد التبديلات من الرتبة $n$ التي لها $m$ من التجاوزات و $k$ من الانخفاضات. احسب جميع قيم $h(n, m, k)$ لقيمة $n$ معطاة. نظراً لأن الإجابات كبيرة، يكفي أن تطبع قيمها بعد أخذ باقي القسمة على $M$.

الإدخال

سطر واحد يحتوي على عددين صحيحين موجبين $n$ و $M$، يمثلان رتبة التبديلة ومعامل باقي القسمة.

الإخراج

اطبع $n$ من الأسطر، بحيث يحتوي كل سطر على $n$ من الأعداد، حيث يمثل العدد في السطر $i$ والعمود $j$ القيمة $h(n, i-1, j-1) \bmod M$.

أمثلة

أمثلة 1

الإدخال

3 998244353

الإخراج

1 0 0
0 3 1
0 1 0

ملاحظة

• التبديلات التي لها $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

الإخراج

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$.

ملاحظة

يمكنك اختيار استخدام القالب التالي لتسريع عمليات باقي القسمة.

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