#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#define debug(x) cerr << __LINE__ << ' ' << #x << ':' << x << '\n'
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
template<class T> using pque = priority_queue<T, vector<T>, greater<T>>;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr int mod1e9 = 1000000007;
constexpr int mod998 = 998244353;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
constexpr ll ten(int n) { return n ? 10 * ten(n - 1) : 1; };
int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,1,-1 };
void fail() { cout << "-1\n"; exit(0); } void no() { cout << "No\n"; exit(0); }
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }
template<class T> istream &operator >> (istream &s, vector<T> &v) { for (auto &e : v) s >> e; return s; }
template<class T> ostream &operator << (ostream &s, const vector<T> &v) { for (auto &e : v) s << e << ' '; return s; }

struct fastio {
	fastio() {
		cin.tie(0); cout.tie(0);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(20);
		cerr << fixed << setprecision(20);
	}
}fastio_;

template <int mod> class modint {
	int n;
public:
	modint() : n(0) {};
	modint(ll n_) {
		n = n_ % mod;
		if (n < 0) n += mod;
	}
	modint operator -() const { return n > 0 ? mod - n : -n; }
	bool operator == (const modint &m) const { return n == m.n; }
	bool operator != (const modint &m) const { return n != m.n; }
	modint &operator += (const modint &m) { n += m.n; if (n >= mod) n -= mod; return *this; }
	modint &operator -= (const modint &m) { n -= m.n; if (n < 0) n += mod; return *this; }
	modint &operator *= (const modint &m) { n = ll(n) * m.n % mod; return *this; }
	modint &operator /= (const modint &m) { n = ll(n) * m.inv().n % mod; return *this; }
	modint operator +(modint m) const { return modint(*this) += m; }
	modint operator -(modint m) const { return modint(*this) -= m; }
	modint operator *(modint m) const { return modint(*this) *= m; }
	modint operator /(modint m) const { return modint(*this) /= m; }
	modint &operator ++ () { *this += 1; return *this; }
	modint operator ++ (int) { *this += 1; return *this - 1; }
	modint &operator -- () { *this -= 1; return *this; }
	modint operator -- (int) { *this -= 1; return *this + 1; }
	modint inv() const {
		return (*this).pow(mod - 2);
	}
	modint pow(ll b) const {
		modint res = 1, a = modint(*this);
		while (b) {
			if (b & 1) res *= a;
			a *= a;
			b >>= 1;
		}
		return res;
	}
	friend istream &operator >> (istream &s, modint<mod> &a) { s >> a.n; return s; }
	friend ostream &operator << (ostream &s, modint<mod> &a) { s << a.n; return s; }
};

using mint = modint<mod998>;

template<class T> class segtree {
	int n;
	vector<T> data;
	T id = 0;
	T operation(T a, T b) { return a + b; };
public:
	segtree(int _n) {
		n = 1;
		while (n < _n + 2) n <<= 1;
		data = vector<T>(2 * n, id);
	}
	segtree(vector<T> vec) {
		int _n = vec.size();
		n = 1;
		while (n < _n + 2) n <<= 1;
		data = vector<T>(2 * n, id);
		for (int i = 0; i < _n; i++) data[i + n] = vec[i];
		for (int i = n - 1; i >= 1; i--) data[i] = operation(data[i << 1], data[i << 1 | 1]);
	}
	void change(int i, T x) {
		i += n;
		data[i] = x;
		while (i > 1) {
			i >>= 1;
			data[i] = operation(data[i << 1], data[i << 1 | 1]);
		}
	}
	void add(int i, T x) { change(i, data[i + n] + x); }
	T get(int a, int b) {
		T left = id; T right = id;
		a += n; b += n;
		while (a < b) {
			if (a & 1) left = operation(left, data[a++]);
			if (b & 1) right = operation(data[--b], right);
			a >>= 1; b >>= 1;
		}
		return operation(left, right);
	}
	T get_all() { return data[1]; }
	T operator[](int i) { return data[i + n]; }
};

int main() {
	ll n, k;
	cin >> n >> k;
	vector<ll> p(n);
	rep(i, n) {
		cin >> p[i];
		p[i]--;
	}
	segtree<mint> left(n), right(n), cnt(n);
	mint ans = k * (k - 1);
	ans /= 4;
	mint r = (mint)1 - (mint)1 / (mint)k;
	r = (mint)1 / r;
	rep(i, k) {
		left.add(p[i], 1);
		right.add(p[i], 1);
		cnt.add(p[i], 1);
	}
	for (int i = k; i < n; i++) {
		int c = i - k + 1;
		mint x = left.get(0, p[i]);
		x /= r.pow(c);
		x /= 2;
		ans += x;
		mint y = right.get(p[i] + 1, n + 1);
		y /= r.pow(c);
		y /= 2;
		y = cnt.get(p[i] + 1, n + 1) - y;
		ans += y;
		left.add(p[i], r.pow(c));
		right.add(p[i], r.pow(c));
		cnt.add(p[i], 1);
	}
	cout << ans << '\n';
}
### Prompt

Construct a CPP code solution to the problem outlined:

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 <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#define debug(x) cerr << __LINE__ << ' ' << #x << ':' << x << '\n'
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
template<class T> using pque = priority_queue<T, vector<T>, greater<T>>;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr int mod1e9 = 1000000007;
constexpr int mod998 = 998244353;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
constexpr ll ten(int n) { return n ? 10 * ten(n - 1) : 1; };
int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,1,-1 };
void fail() { cout << "-1\n"; exit(0); } void no() { cout << "No\n"; exit(0); }
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }
template<class T> istream &operator >> (istream &s, vector<T> &v) { for (auto &e : v) s >> e; return s; }
template<class T> ostream &operator << (ostream &s, const vector<T> &v) { for (auto &e : v) s << e << ' '; return s; }

struct fastio {
	fastio() {
		cin.tie(0); cout.tie(0);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(20);
		cerr << fixed << setprecision(20);
	}
}fastio_;

template <int mod> class modint {
	int n;
public:
	modint() : n(0) {};
	modint(ll n_) {
		n = n_ % mod;
		if (n < 0) n += mod;
	}
	modint operator -() const { return n > 0 ? mod - n : -n; }
	bool operator == (const modint &m) const { return n == m.n; }
	bool operator != (const modint &m) const { return n != m.n; }
	modint &operator += (const modint &m) { n += m.n; if (n >= mod) n -= mod; return *this; }
	modint &operator -= (const modint &m) { n -= m.n; if (n < 0) n += mod; return *this; }
	modint &operator *= (const modint &m) { n = ll(n) * m.n % mod; return *this; }
	modint &operator /= (const modint &m) { n = ll(n) * m.inv().n % mod; return *this; }
	modint operator +(modint m) const { return modint(*this) += m; }
	modint operator -(modint m) const { return modint(*this) -= m; }
	modint operator *(modint m) const { return modint(*this) *= m; }
	modint operator /(modint m) const { return modint(*this) /= m; }
	modint &operator ++ () { *this += 1; return *this; }
	modint operator ++ (int) { *this += 1; return *this - 1; }
	modint &operator -- () { *this -= 1; return *this; }
	modint operator -- (int) { *this -= 1; return *this + 1; }
	modint inv() const {
		return (*this).pow(mod - 2);
	}
	modint pow(ll b) const {
		modint res = 1, a = modint(*this);
		while (b) {
			if (b & 1) res *= a;
			a *= a;
			b >>= 1;
		}
		return res;
	}
	friend istream &operator >> (istream &s, modint<mod> &a) { s >> a.n; return s; }
	friend ostream &operator << (ostream &s, modint<mod> &a) { s << a.n; return s; }
};

using mint = modint<mod998>;

template<class T> class segtree {
	int n;
	vector<T> data;
	T id = 0;
	T operation(T a, T b) { return a + b; };
public:
	segtree(int _n) {
		n = 1;
		while (n < _n + 2) n <<= 1;
		data = vector<T>(2 * n, id);
	}
	segtree(vector<T> vec) {
		int _n = vec.size();
		n = 1;
		while (n < _n + 2) n <<= 1;
		data = vector<T>(2 * n, id);
		for (int i = 0; i < _n; i++) data[i + n] = vec[i];
		for (int i = n - 1; i >= 1; i--) data[i] = operation(data[i << 1], data[i << 1 | 1]);
	}
	void change(int i, T x) {
		i += n;
		data[i] = x;
		while (i > 1) {
			i >>= 1;
			data[i] = operation(data[i << 1], data[i << 1 | 1]);
		}
	}
	void add(int i, T x) { change(i, data[i + n] + x); }
	T get(int a, int b) {
		T left = id; T right = id;
		a += n; b += n;
		while (a < b) {
			if (a & 1) left = operation(left, data[a++]);
			if (b & 1) right = operation(data[--b], right);
			a >>= 1; b >>= 1;
		}
		return operation(left, right);
	}
	T get_all() { return data[1]; }
	T operator[](int i) { return data[i + n]; }
};

int main() {
	ll n, k;
	cin >> n >> k;
	vector<ll> p(n);
	rep(i, n) {
		cin >> p[i];
		p[i]--;
	}
	segtree<mint> left(n), right(n), cnt(n);
	mint ans = k * (k - 1);
	ans /= 4;
	mint r = (mint)1 - (mint)1 / (mint)k;
	r = (mint)1 / r;
	rep(i, k) {
		left.add(p[i], 1);
		right.add(p[i], 1);
		cnt.add(p[i], 1);
	}
	for (int i = k; i < n; i++) {
		int c = i - k + 1;
		mint x = left.get(0, p[i]);
		x /= r.pow(c);
		x /= 2;
		ans += x;
		mint y = right.get(p[i] + 1, n + 1);
		y /= r.pow(c);
		y /= 2;
		y = cnt.get(p[i] + 1, n + 1) - y;
		ans += y;
		left.add(p[i], r.pow(c));
		right.add(p[i], r.pow(c));
		cnt.add(p[i], 1);
	}
	cout << ans << '\n';
}
```