#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

constexpr int64 P = 998244353;

struct FiniteField {
 private:
  int64 x;
 public:
  FiniteField(int64 raw_x) : x(raw_x) {
    if (x >= P || x < 0) {
    x %= P;
    if (x < 0) x += P;
  }
}
  FiniteField() : x(0) {}
  int64 Value() const { return x; }
  inline FiniteField operator+(FiniteField o) const {
    FiniteField r(*this); r += o; return r;
  }
  inline FiniteField operator-(FiniteField o) const {
    FiniteField r(*this); r -= o; return r;
  }
  inline FiniteField operator* (FiniteField o) const {
    FiniteField r(*this); r *= o; return r;
  }
  inline FiniteField operator/ (FiniteField o) const {
    FiniteField r(*this); r /= o; return r;
  }
  inline void operator+= (FiniteField o) { x = (x + o.x) % P; }
  inline void operator-= (FiniteField o) { x = (x + P - o.x) % P; }
  inline void operator*= (FiniteField o) { x = (x * o.x) % P; }
  void operator/=(FiniteField o) {
    int64 p = P - 2; while (p) { if (p % 2) { *this *= o; } o *= o; p /= 2; }
  }
};
ostream& operator<<(ostream& s, const FiniteField& x) { s << x.Value(); return s; }

template <typename T>
class SegmentTree {
 private:
  function<T(T, T)> merge_fn;
  T empty_value;
  vector<T> nodes;
  int num_nodes;

  // Returns the fold of overwrap between [node_l, node_r) and [l, r).
  // nodes[node_index] needs to correspond to [node_l, node_r).
  T GetRangeInternal(int node_index, int node_l, int node_r, int l, int r) {
    if (node_r <= l || r <= node_l) return empty_value;
    if (l <= node_l && node_r <= r) return nodes[node_index];
    int node_m = (node_l + node_r) / 2;
    return merge_fn(
        GetRangeInternal(2 * node_index, node_l, node_m, l, r),
        GetRangeInternal(2 * node_index + 1, node_m, node_r, l, r));
  }

 public:
  // Arguments:
  // in_merge: The function to merge two values. It should be a monoid.
  // in_empty_value: The identity of the monoid.
  // xs: The initial values.
  SegmentTree(
      function<T(T, T)> merge_fn, T empty_value, const vector<T>& xs) :
          merge_fn(merge_fn), empty_value(empty_value) {
    int n = xs.size();
    num_nodes = 1;
    while (num_nodes < n) num_nodes *= 2;
    num_nodes *= 2;
    nodes = vector<T>(num_nodes, empty_value);
    for (int i = 0; i < xs.size(); ++i) {
      nodes[num_nodes / 2 + i] = xs[i];
    }
    for (int i = num_nodes / 2 - 1; i >= 1; i--) {
      nodes[i] = merge_fn(nodes[2 * i], nodes[2 * i + 1]);
    }
  }

  // Updates the i-th element to x.
  void Update(int i, T x) {
    nodes[num_nodes / 2 + i] = x;
    for (int cur = (num_nodes / 2 + i) / 2; cur > 0; cur /= 2) {
      nodes[cur] = merge_fn(nodes[2 * cur], nodes[2 * cur + 1]);
    }
  }

  // Returns the value of the range [l, r) merged by merge_fn.
  T GetRange(int l, int r) {
    return GetRangeInternal(1, 0, num_nodes / 2, l, r);
  }

  T Get(int i) {
    return nodes[num_nodes / 2 + i];
  }
};

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

  const FiniteField half = FiniteField(1) / FiniteField(2);

  auto add_fn = [](FiniteField x1, FiniteField x2) -> FiniteField {
    return x1 + x2;
  };

  int n, k;
  cin >> n >> k;

  FiniteField p = FiniteField(k - 1) / FiniteField(k);

  vector<FiniteField> powers(n + 2);
  powers[0] = 1;
  for (int i = 1; i <= n + 1; i++) {
    powers[i] = powers[i - 1] * p;
  }

  vector<int> ps(n);
  vector<int> v_to_position(n);
  for (int i = 0; i < n; i++) {
    cin >> ps[i];
    ps[i]--;
    v_to_position[ps[i]] = i;
  }

  FiniteField ans = 0;
  SegmentTree<FiniteField> tree1(add_fn, 0, vector<FiniteField>(n, 0));
  SegmentTree<FiniteField> tree2(add_fn, 0, vector<FiniteField>(n, 0));
  for (int i = 0; i < n; i++) {
    int position = v_to_position[i];
    // cout << "position: " << position << endl;

    int s = max(position + 1, k);
    if (s >= n) {
      tree1.Update(position, 1);
      tree2.Update(position, powers[position]);
      continue;
    }

    int count = n - s;
    FiniteField base = half * p * (FiniteField(1) - powers[count]) / (FiniteField(1) - p);

    // cout << base * FiniteField(4) << endl;

    base += tree1.GetRange(s, n);
    base -= tree2.GetRange(s, n) / powers[s - 1];

    ans += base;

    tree1.Update(position, 1);
    tree2.Update(position, powers[position]);

    // cout << base * FiniteField(4) << endl;
  }

  // cout << half * 2 << endl;
  // cout << half * FiniteField(k) << endl;
  // cout << half * FiniteField(k) * FiniteField(k - 1) << endl;
  ans += half * half * FiniteField(k) * FiniteField(k - 1);
  // cout << ans * FiniteField(4) << endl;
  cout << ans << endl;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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 <bits/stdc++.h>

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

constexpr int64 P = 998244353;

struct FiniteField {
 private:
  int64 x;
 public:
  FiniteField(int64 raw_x) : x(raw_x) {
    if (x >= P || x < 0) {
    x %= P;
    if (x < 0) x += P;
  }
}
  FiniteField() : x(0) {}
  int64 Value() const { return x; }
  inline FiniteField operator+(FiniteField o) const {
    FiniteField r(*this); r += o; return r;
  }
  inline FiniteField operator-(FiniteField o) const {
    FiniteField r(*this); r -= o; return r;
  }
  inline FiniteField operator* (FiniteField o) const {
    FiniteField r(*this); r *= o; return r;
  }
  inline FiniteField operator/ (FiniteField o) const {
    FiniteField r(*this); r /= o; return r;
  }
  inline void operator+= (FiniteField o) { x = (x + o.x) % P; }
  inline void operator-= (FiniteField o) { x = (x + P - o.x) % P; }
  inline void operator*= (FiniteField o) { x = (x * o.x) % P; }
  void operator/=(FiniteField o) {
    int64 p = P - 2; while (p) { if (p % 2) { *this *= o; } o *= o; p /= 2; }
  }
};
ostream& operator<<(ostream& s, const FiniteField& x) { s << x.Value(); return s; }

template <typename T>
class SegmentTree {
 private:
  function<T(T, T)> merge_fn;
  T empty_value;
  vector<T> nodes;
  int num_nodes;

  // Returns the fold of overwrap between [node_l, node_r) and [l, r).
  // nodes[node_index] needs to correspond to [node_l, node_r).
  T GetRangeInternal(int node_index, int node_l, int node_r, int l, int r) {
    if (node_r <= l || r <= node_l) return empty_value;
    if (l <= node_l && node_r <= r) return nodes[node_index];
    int node_m = (node_l + node_r) / 2;
    return merge_fn(
        GetRangeInternal(2 * node_index, node_l, node_m, l, r),
        GetRangeInternal(2 * node_index + 1, node_m, node_r, l, r));
  }

 public:
  // Arguments:
  // in_merge: The function to merge two values. It should be a monoid.
  // in_empty_value: The identity of the monoid.
  // xs: The initial values.
  SegmentTree(
      function<T(T, T)> merge_fn, T empty_value, const vector<T>& xs) :
          merge_fn(merge_fn), empty_value(empty_value) {
    int n = xs.size();
    num_nodes = 1;
    while (num_nodes < n) num_nodes *= 2;
    num_nodes *= 2;
    nodes = vector<T>(num_nodes, empty_value);
    for (int i = 0; i < xs.size(); ++i) {
      nodes[num_nodes / 2 + i] = xs[i];
    }
    for (int i = num_nodes / 2 - 1; i >= 1; i--) {
      nodes[i] = merge_fn(nodes[2 * i], nodes[2 * i + 1]);
    }
  }

  // Updates the i-th element to x.
  void Update(int i, T x) {
    nodes[num_nodes / 2 + i] = x;
    for (int cur = (num_nodes / 2 + i) / 2; cur > 0; cur /= 2) {
      nodes[cur] = merge_fn(nodes[2 * cur], nodes[2 * cur + 1]);
    }
  }

  // Returns the value of the range [l, r) merged by merge_fn.
  T GetRange(int l, int r) {
    return GetRangeInternal(1, 0, num_nodes / 2, l, r);
  }

  T Get(int i) {
    return nodes[num_nodes / 2 + i];
  }
};

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

  const FiniteField half = FiniteField(1) / FiniteField(2);

  auto add_fn = [](FiniteField x1, FiniteField x2) -> FiniteField {
    return x1 + x2;
  };

  int n, k;
  cin >> n >> k;

  FiniteField p = FiniteField(k - 1) / FiniteField(k);

  vector<FiniteField> powers(n + 2);
  powers[0] = 1;
  for (int i = 1; i <= n + 1; i++) {
    powers[i] = powers[i - 1] * p;
  }

  vector<int> ps(n);
  vector<int> v_to_position(n);
  for (int i = 0; i < n; i++) {
    cin >> ps[i];
    ps[i]--;
    v_to_position[ps[i]] = i;
  }

  FiniteField ans = 0;
  SegmentTree<FiniteField> tree1(add_fn, 0, vector<FiniteField>(n, 0));
  SegmentTree<FiniteField> tree2(add_fn, 0, vector<FiniteField>(n, 0));
  for (int i = 0; i < n; i++) {
    int position = v_to_position[i];
    // cout << "position: " << position << endl;

    int s = max(position + 1, k);
    if (s >= n) {
      tree1.Update(position, 1);
      tree2.Update(position, powers[position]);
      continue;
    }

    int count = n - s;
    FiniteField base = half * p * (FiniteField(1) - powers[count]) / (FiniteField(1) - p);

    // cout << base * FiniteField(4) << endl;

    base += tree1.GetRange(s, n);
    base -= tree2.GetRange(s, n) / powers[s - 1];

    ans += base;

    tree1.Update(position, 1);
    tree2.Update(position, powers[position]);

    // cout << base * FiniteField(4) << endl;
  }

  // cout << half * 2 << endl;
  // cout << half * FiniteField(k) << endl;
  // cout << half * FiniteField(k) * FiniteField(k - 1) << endl;
  ans += half * half * FiniteField(k) * FiniteField(k - 1);
  // cout << ans * FiniteField(4) << endl;
  cout << ans << endl;
}
```