Code : Ascent and Prefix Maxima

// Refer 1988 F. Heartbeat

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

void solve(int maxn) {
    vector<vector<mint>> dp(maxn + 2, vector<mint>(maxn + 2, 0));
    // dp[i][j] is the number of permutations with i prefix maximas and
    // j ascents.

    // For n = 1, the only permutation is (1).
    dp[1][0] = 1;

    // At the start of each iteration of the loop, we have n elements and we
    // try to insert an additional element, making the new size as n + 1.
    for (int n = 1; n < maxn; n++) {
        vector<vector<mint>> ndp(maxn + 2, vector<mint>(maxn + 2, 0));

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                // Promote the permutation [1 ... N] to [2 ... N + 1]
                // Insert a 1 at some position.

                // Insert a 1 to the left of an ascent or to the end of array.
                ndp[i][j] += (j + 1) * dp[i][j];

                // Insert a 1 anywhere such that it is not to the left of an
                // ascent.
                // There are j ascent elements, so (n - j) non-ascent elements.
                // However, the first element also lies in this (n - j) bucket.
                // Hence, we handle it separately.
                ndp[i][j + 1] += (n - j - 1) * dp[i][j];

                // Insert a 1 at the start.
                ndp[i + 1][j + 1] += dp[i][j];
            }
        }
        swap(dp, ndp);
    }

    for (int i = 0; i <= maxn; i++) {
        for (int j = 0; j <= maxn; j++) {
            if (dp[i][j].val() > 0) {
                cout << dp[i][j].val() << " ";
            }
        }
    }

    for (int i = 0; i <= maxn; i++) {
        for (int j = 0; j <= maxn; j++) {
            if (dp[i][j].val() > 0) {
                cout << dp[i][j].val() << " ";
            }
        }
    }
    cout << endl;
}

void count(int n) {
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        p[i] = i + 1;
    }

    map<pair<int, int>, int> count;
    do {
        int pmax = 0, asc = 0;
        int mx = -1;
        for (int i = 0; i < n; i++) {
            mx = max(mx, p[i]);
            if (mx == p[i]) {
                pmax++;
            }
            if (i && p[i] > p[i - 1]) {
                asc++;
            }
        }
        count[{pmax, asc}]++;
    } while (next_permutation(p.begin(), p.end()));

    for (auto &kv : count) {
        cout << kv.second << " ";
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    count(n);
    solve(n);
}