#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

#define P 998244353
#define N_MAX 10000000
ll fac[N_MAX+1], inv[N_MAX+1], finv[N_MAX+1];
ll comb(ll n, ll k){
  if(n<0||k<0||n<k) return 0;
  return (((fac[n]*finv[n-k])%P)*finv[k])%P;
}
ll perm(ll n, ll k){
  if(n<0||k<0||n<k) return 0;
  return (fac[n]*finv[n-k])%P;
}
void init(){
  fac[0] = finv[0] = fac[1] = finv[1] = inv[1] = 1;
  for(int i = 2; i <= N_MAX; i++){
    fac[i] = (fac[i-1]*i)%P;
    inv[i] = ((-(P/i)*inv[P%i])%P+P)%P;
    finv[i] = (finv[i-1]*inv[i])%P;
  }
}
ll pp(ll a, ll b){ return (a * b)%P;}
ll mpow(ll a, ll b, ll p = -1){
  ll ret = 1, num = a;
  while(b>0){
    if(b&1) ret = (ret*num)%p;
    num = (num*num)%p;
    b /= 2;
  }
  return ret;
}


struct LazySegmentTree {
private:
    int n;
    vector<ll> node, lazy;
public:
    LazySegmentTree(vector<ll> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 1);
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = (node[i*2+1] + node[i*2+2])%P;
    }
    void eval(int k, int l, int r) {
        if(lazy[k] != 1) {
            node[k] = (node[k] * lazy[k])%P;
            if(r - l > 1) {
                lazy[2*k+1] = (lazy[2*k+1] * lazy[k])%P;
                lazy[2*k+2] = (lazy[2*k+2] * lazy[k])%P;
            }
            lazy[k] = 1;
        }
    }
    void ml(int a, int b, ll x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] = (lazy[k] * x)%P;
            eval(k, l, r);
        }
        else {
            ml(a, b, x, 2*k+1, l, (l+r)/2);
            ml(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = (node[2*k+1] + node[2*k+2])%P;
        }
    }

    void add(ll x, int k){
      getsum(k, k+1);
      k += n-1;
      node[k] = (node[k] + x)%P;
      while(k){
        k = (k-1)/2;
        node[k] = (node[2*k+1] + node[2*k+2])%P;
      }
    }

    ll getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return (vl + vr)%P;
    }
};

struct BIT{
  ll M=1;
  vector<ll> dat;
  BIT(ll N){
    if(N<=1) N = 2;
    while(N>M) M*=2;
    dat.resize(M*2-1, 0);
  }
  void update(ll x, ll k){
    for(int i=k+1;i<=M;i+=(i&(-i))){
      dat[i] += x;
    }
  }
  ll sum(ll r){
    ll ret = 0;
    for(int k=r;k>0;k-=(k&(-k))) ret += dat[k];
    return ret;
  }

  ll query(ll l, ll r){
    return sum(r) - sum(l);
  }
};

int main(){
  ll n, k;std::cin >> n >> k;
  init();
  vll p(n);
  re(i, n) {
    scanf("%lld", &p[i]);
    p[i]--;
  }
  BIT bt(n);
  LazySegmentTree seg(vll(n, 0));

  ll ans = 0;
  for(int i=0;i<k;i++){
    //iまで到達する確率
    ll lef = seg.getsum(0, p[i]);//巻き込まれて1/2   -> i<kなら1/2 異なれば
    ll ri  = seg.getsum(p[i], n);//巻き込まれない or 巻き込まれて1/2
    ll num = bt.query(p[i], n);
    ll psum = ((lef * inv[2])%P + (ri * inv[2])%P + (num - ri + P)%P)%P;
    ans = (ans + psum)%P;
    seg.add(1, p[i]);
    bt.update(1, p[i]);
  }

  ll x = ((k-1LL) * inv[k])%P;
  for(int i=k;i<n;i++){
    seg.ml(0, n+1, x);
    //iまで到達する確率
    ll lef = seg.getsum(0, p[i]);//巻き込まれて1/2   -> i<kなら1/2 異なれば
    ll ri  = seg.getsum(p[i], n);//巻き込まれない or 巻き込まれて1/2
    ll num = bt.query(p[i], n);
    ll psum = ((lef * inv[2])%P + (ri * inv[2])%P + (num - ri + P)%P)%P;
    //for(int j=0;j<n;j++) std::cout << seg.getsum(j, j+1) << (j==n-1?"\n":" ");
    //std::cout << lef << " " << ri << '\n';
    ans = (ans + psum)%P;
    seg.add(1, p[i]);
    bt.update(1, p[i]);
  }
  std::cout << ans << '\n';
}

### Prompt

Create a solution in CPP for the following problem:

Given are a permutation p_1, p_2, \dots, p_N of (1, 2, ..., N) and an integer K. Maroon performs the following operation for i = 1, 2, \dots, N - K + 1 in this order:

* Shuffle p_i, p_{i + 1}, \dots, p_{i + K - 1} uniformly randomly.



Find the expected value of the inversion number of the sequence after all the operations are performed, and print it modulo 998244353.

More specifically, from the constraints of this problem, it can be proved that the expected value is always a rational number, which can be represented as an irreducible fraction \frac{P}{Q}, and that the integer R that satisfies R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 is uniquely determined. Print this R.

Here, the inversion number of a sequence a_1, a_2, \dots, a_N is defined to be the number of ordered pairs (i, j) that satisfy i < j, a_i > a_j.

Constraints

* 2 \leq N \leq 200,000
* 2 \leq K \leq N
* (p_1, p_2, \dots, p_N) is a permutation of (1, 2, \dots, N).
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N K
p_1 p_2 ... p_N


Output

Print the expected value modulo 998244353.

Examples

Input

3 2
1 2 3


Output

1


Input

10 3
1 8 4 9 2 3 7 10 5 6


Output

164091855

### Response

```cpp
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

#define P 998244353
#define N_MAX 10000000
ll fac[N_MAX+1], inv[N_MAX+1], finv[N_MAX+1];
ll comb(ll n, ll k){
  if(n<0||k<0||n<k) return 0;
  return (((fac[n]*finv[n-k])%P)*finv[k])%P;
}
ll perm(ll n, ll k){
  if(n<0||k<0||n<k) return 0;
  return (fac[n]*finv[n-k])%P;
}
void init(){
  fac[0] = finv[0] = fac[1] = finv[1] = inv[1] = 1;
  for(int i = 2; i <= N_MAX; i++){
    fac[i] = (fac[i-1]*i)%P;
    inv[i] = ((-(P/i)*inv[P%i])%P+P)%P;
    finv[i] = (finv[i-1]*inv[i])%P;
  }
}
ll pp(ll a, ll b){ return (a * b)%P;}
ll mpow(ll a, ll b, ll p = -1){
  ll ret = 1, num = a;
  while(b>0){
    if(b&1) ret = (ret*num)%p;
    num = (num*num)%p;
    b /= 2;
  }
  return ret;
}


struct LazySegmentTree {
private:
    int n;
    vector<ll> node, lazy;
public:
    LazySegmentTree(vector<ll> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 1);
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = (node[i*2+1] + node[i*2+2])%P;
    }
    void eval(int k, int l, int r) {
        if(lazy[k] != 1) {
            node[k] = (node[k] * lazy[k])%P;
            if(r - l > 1) {
                lazy[2*k+1] = (lazy[2*k+1] * lazy[k])%P;
                lazy[2*k+2] = (lazy[2*k+2] * lazy[k])%P;
            }
            lazy[k] = 1;
        }
    }
    void ml(int a, int b, ll x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] = (lazy[k] * x)%P;
            eval(k, l, r);
        }
        else {
            ml(a, b, x, 2*k+1, l, (l+r)/2);
            ml(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = (node[2*k+1] + node[2*k+2])%P;
        }
    }

    void add(ll x, int k){
      getsum(k, k+1);
      k += n-1;
      node[k] = (node[k] + x)%P;
      while(k){
        k = (k-1)/2;
        node[k] = (node[2*k+1] + node[2*k+2])%P;
      }
    }

    ll getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return (vl + vr)%P;
    }
};

struct BIT{
  ll M=1;
  vector<ll> dat;
  BIT(ll N){
    if(N<=1) N = 2;
    while(N>M) M*=2;
    dat.resize(M*2-1, 0);
  }
  void update(ll x, ll k){
    for(int i=k+1;i<=M;i+=(i&(-i))){
      dat[i] += x;
    }
  }
  ll sum(ll r){
    ll ret = 0;
    for(int k=r;k>0;k-=(k&(-k))) ret += dat[k];
    return ret;
  }

  ll query(ll l, ll r){
    return sum(r) - sum(l);
  }
};

int main(){
  ll n, k;std::cin >> n >> k;
  init();
  vll p(n);
  re(i, n) {
    scanf("%lld", &p[i]);
    p[i]--;
  }
  BIT bt(n);
  LazySegmentTree seg(vll(n, 0));

  ll ans = 0;
  for(int i=0;i<k;i++){
    //iまで到達する確率
    ll lef = seg.getsum(0, p[i]);//巻き込まれて1/2   -> i<kなら1/2 異なれば
    ll ri  = seg.getsum(p[i], n);//巻き込まれない or 巻き込まれて1/2
    ll num = bt.query(p[i], n);
    ll psum = ((lef * inv[2])%P + (ri * inv[2])%P + (num - ri + P)%P)%P;
    ans = (ans + psum)%P;
    seg.add(1, p[i]);
    bt.update(1, p[i]);
  }

  ll x = ((k-1LL) * inv[k])%P;
  for(int i=k;i<n;i++){
    seg.ml(0, n+1, x);
    //iまで到達する確率
    ll lef = seg.getsum(0, p[i]);//巻き込まれて1/2   -> i<kなら1/2 異なれば
    ll ri  = seg.getsum(p[i], n);//巻き込まれない or 巻き込まれて1/2
    ll num = bt.query(p[i], n);
    ll psum = ((lef * inv[2])%P + (ri * inv[2])%P + (num - ri + P)%P)%P;
    //for(int j=0;j<n;j++) std::cout << seg.getsum(j, j+1) << (j==n-1?"\n":" ");
    //std::cout << lef << " " << ri << '\n';
    ans = (ans + psum)%P;
    seg.add(1, p[i]);
    bt.update(1, p[i]);
  }
  std::cout << ans << '\n';
}

```