In this editorial, we let \(_nP_r\) denote the number of ways (permutations) to select and arrange \(r\) items out of \(n\).

Let’s consider an example \(N=6, K=4, P=(4,6,5,1)\). When counting manually, you would first deal with:

• Sequences in the dictionary \(s\) that start with \(1\)
• Sequences in the dictionary \(s\) that start with \(2\)
• Sequences in the dictionary \(s\) that start with \(3\)

Next, you would handle:

• Sequences in the dictionary \(s\) with the prefix \((4,1)\)
• Sequences in the dictionary \(s\) with the prefix \((4,2)\)
• Sequences in the dictionary \(s\) with the prefix \((4,3)\)
• Sequences in the dictionary \(s\) with the prefix \((4,5)\)

Following this intuition, let’s consider how to solve the problem.

For \(i = 1,2,\dots,K\), perform the following steps:

• Deal with sequences in dictionary \(s\) where the first \(i-1\) elements match \(P\) and the \(i\)-th element is between \(1\) and \(P_i-1\).
  • Let \(c\) be the count of integers between \(1\) and \(P_i-1\) that are not in the first \(i-1\) elements of \(P\).
  • For integers between \(1\) and \(P_i-1\) that are not in the first \(i-1\) elements of \(P\), each appears \(_{N-i}P_{K-i} + (c-1) \times _{N-i}P_{K-i} \times \frac{K-i}{N-i}\) times.
  • For integers between \(P_i\) and \(N\) that are not in the first \(i-1\) elements of \(P\), each appears \(c \times _{N-i}P_{K-i} \times \frac{K-i}{N-i}\) times.
  • (Note: The above two formulas include division by zero when \(N=K\), so handle appropriately.)
• When completing the step for \(i\), the total occurrence of \(P_i\) is confirmed as “those considered up to this point” + “the total number of sequences to be considered later, \(\varDelta_i\) (sequences in the dictionary \(s\) that are lexicographically less than or equal to \(P\) and the first \(i\) terms match \(P\))”.

The occurrence counts of values not in \(P\) can be confirmed when completing the step for \(i=K\).

If we ignore the time complexity, the answer to the problem has already been found.

Now, let’s consider speeding up the process. The key points to notice are:

• \(\varDelta_i\) can be calculated in descending order of \(i\) in \(O(K \log N)\) time in total.
• Additions of the form “each of the integers between \(1\) and \(P_i-1\) that are not in the first \(i-1\) elements of \(P\) appears \(\alpha\) times” can be treated as simple range additions by ignoring the part “in the first \(i-1\) elements of \(P\)” since the total occurrence counts of these are already confirmed.

To apply this optimization, it is necessary to prepare a data structure capable of range addition and point retrieval (for example, the lazy segment tree lazy_segtree from ACL can be used).

Thus, this problem can be solved in \(O(N \log N)\) time complexity. As can be inferred from the problem being recursively structured, recursion is convenient for the overall implementation.
Note: Depending on the approach, recursion might go up to \(3 \times 10^5\) levels, so care might be needed when executing locally. In such cases, code testing is also handy. [Translator’s Note: I’m not sure of the validity of this statement. For example, if you use Linux or WSL, ulimit -s unlimited would work.]

Sample Implementation (C++):

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

using namespace std;
using namespace atcoder;

#define mod 998244353
#define FACSIZE 1048576

long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}

long long modular_inverse(long long n){
  return power(n,mod-2);
}

long long factorial[FACSIZE];
long long invfact[FACSIZE];

void cfact(){
  long long i;
  factorial[0]=1;
  factorial[1]=1;
  for(i=2;i<FACSIZE;i++){
    factorial[i]=factorial[i-1]*i;
    factorial[i]%=mod;
  }
  invfact[FACSIZE-1]=modular_inverse(factorial[FACSIZE-1]);
  for(i=FACSIZE-2;i>=0;i--){
    invfact[i]=invfact[i+1]*(i+1);
    invfact[i]%=mod;
  }
}

long long calcnCr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}

long long calcnPr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*invfact[n-k])%mod;
}

// https://betrue12.hateblo.jp/entry/2020/09/23/005940#%E5%8C%BA%E9%96%93%E5%8A%A0%E7%AE%97%E5%8C%BA%E9%96%93%E5%92%8C%E5%8F%96%E5%BE%97
struct S{
    long long value;
    long long size;
};
using F = long long;

S op(S a, S b){ return {(a.value+b.value)%mod, (a.size+b.size)%mod}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){ return {(x.value + f*x.size)%mod, x.size}; }
F composition(F f, F g){ return (f+g)%mod; }
F id(){ return 0; }

long long n,k;
vector<long long> p;
vector<long long> res;
lazy_segtree<S, op, e, F, mapping, composition, id> seg;
lazy_segtree<S, op, e, F, mapping, composition, id> segpt;

long long rep(long long pos){
  if(pos==k){
    for(long long i=0;i<n;i++){
      if(segpt.get(i).value==1){
        res[i]=seg.get(i).value;
      }
    }
    return 1;
  }

  long long rank=segpt.prod(0,p[pos]).value;
  segpt.apply(p[pos],-1);

  long long unit=calcnPr(n-pos-1,k-pos-1);
  long long exist=(((unit*(k-pos-1))%mod)*modular_inverse(n-pos-1))%mod;
  long long smaller,larger;

  // actually, this case work isn't required
  if(pos==k-1){
    smaller=1;
    larger=0;
  }
  else{
    smaller=((exist*(rank-1))+unit)%mod;
    larger=(exist*rank)%mod;
  }

  seg.apply(0,p[pos],smaller);
  seg.apply(p[pos],n,larger);

  res[p[pos]]=seg.get(p[pos]).value;
  long long upper=(rank*unit)%mod;
  long long lower=rep(pos+1);
  res[p[pos]]+=lower;
  res[p[pos]]%=mod;
  return (upper+lower)%mod;
}

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

  cin >> n >> k;
  p.resize(k);
  for(auto &nx : p){
    cin >> nx;
    nx--;
  }
  res.resize(n);

  vector<S> ini(n,{0,1});
  lazy_segtree<S, op, e, F, mapping, composition, id> inis(ini);
  seg=inis;
  segpt=inis;
  segpt.apply(0,n,1);

  rep(0);

  for(auto &nx : res){
    cout << nx%mod << "\n";
  }
  return 0;
}