You are given an array A of length n. You have to ...

Key observation

If all A[i] are distinct, replacing every value with its rank (1 … n in increasing-A order) doesn’t change any strict “ < ” comparisons.
After that replacement every permutation of indices becomes a permutation of the ranks 1 … n, and

“A[p[i]] < A[p[i+1]]” ⇔ “ rank [p[i]] < rank [p[i+1]]”.

So we are counting permutations of 1 … n having exactly k ascents (positions where the sequence increases).
Those numbers are the classical Eulerian numbers ⟨ n, k ⟩.

⟨ n, k ⟩ = number of permutations of n with exactly k ascents.

They satisfy the recurrence

text
⟨1,0⟩ = 1
⟨n,k⟩ = (n-k)·⟨n-1,k-1⟩ + (k+1)·⟨n-1,k⟩  for 1 ≤ k ≤ n−1

Computing this for all k up to n−1 takes O(n²) time and O(n) memory, perfectly fine for competitive-programming constraints (n ≤ 5 000, 10 000, …).
Everything is done modulo 998 244 353.

---

Algorithm

1. Read n, k and the array A.
   If duplicates are allowed, first check whether any two values are equal.
   • If duplicates exist, the strict-less statistic becomes harder (it is no longer the classical Eulerian problem). A full solution needs a multiset-Eulerian DP that keeps track of value-groups; that is beyond a short answer, but for distinct A—the vast majority of tasks—skip this step.
2. Pre-compute Eulerian numbers up to n with the recurrence above.
3. Output ⟨n,k⟩ (mod 998 244 353); if k ≥ n print 0.

---

Reference C++17 implementation

cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int addmod(long long a){ return int(a%MOD); }

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;                          // 1 ≤ n ≤ ? (problem limits)
    if(!(cin >> n >> k)) return 0;
    vector<long long> A(n);
    for(auto &x: A) cin >> x;          // values are irrelevant if all distinct

    if(k >= n){ cout << 0 << '\n'; return 0; }

    vector<int> prev(n), cur(n);

    prev[0] = 1;                       // ⟨1,0⟩
    for(int i = 2; i <= n; ++i){
        fill(cur.begin(), cur.begin()+i, 0);
        for(int j = 0; j <= i-2; ++j){
            // term (i-j)·⟨i-1,j⟩    → ascent count j+1
            long long t1 = 1LL*(i - j)*prev[j] % MOD;
            cur[j+1] = (cur[j+1] + t1) % MOD;

            // term (j+1)·⟨i-1,j⟩ → ascent count stays j
            long long t2 = 1LL*(j + 1)*prev[j] % MOD;
            cur[j]   = (cur[j]   + t2) % MOD;
        }
        swap(prev, cur);
    }
    cout << prev[k] << '\n';
    return 0;
}

Complexities

step	time	memory
DP	O(n²)	O(n)
total	O(n²)	O(n)

---

What if A may contain duplicates?

Then we are counting permutations of multisets with a given number of strict ascents—a “multiset Eulerian” problem. A workable approach is:

• Compress equal-value positions into groups of sizes s₁, s₂, ….
• Process groups in rising-value order with a DP on
  dp[len][asc] = ways after placing the first len elements,
  and, for each new group, insert its members in all possible gaps while tracking how many new (small → large) transitions are created.
• The transition from one group to the next is basically a convolution that can be sped up with NTT if tight limits require O(n log² n).

Because this requires a longer derivation, most contest setters phrase the task with distinct A[i], in which case the simple Eulerian solution above is accepted and optimal.