#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
//const int MOD = 1000000007;
const int MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const double pi = acos(-1.0);
const double EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

template<int mod>
struct Mod_Int{
    ll x;

    Mod_Int() : x(0) {}

    Mod_Int(ll y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    Mod_Int &operator += (const Mod_Int &p){
        x = (x + p.x) % mod;
        return *this;
    }

    Mod_Int &operator -= (const Mod_Int &p){
        x = (x + mod - p.x) % mod;
        return *this;
    }

    Mod_Int &operator *= (const Mod_Int &p){
        x = (x * p.x) % mod;
        return *this;
    }

    Mod_Int &operator /= (const Mod_Int &p){
        *this *= p.inverse();
        return *this;
    }

    Mod_Int &operator ++ () {return *this += Mod_Int(1);}

    Mod_Int operator ++ (int){
        Mod_Int tmp = *this;
        ++*this;
        return tmp;
    }

    Mod_Int &operator -- () {return *this -= Mod_Int(1);}

    Mod_Int operator -- (int){
        Mod_Int tmp = *this;
        --*this;
        return tmp;
    }

    Mod_Int operator - () const {return Mod_Int(-x);}

    Mod_Int operator + (const Mod_Int &p) const {return Mod_Int(*this) += p;}

    Mod_Int operator - (const Mod_Int &p) const {return Mod_Int(*this) -= p;}

    Mod_Int operator * (const Mod_Int &p) const {return Mod_Int(*this) *= p;}

    Mod_Int operator / (const Mod_Int &p) const {return Mod_Int(*this) /= p;}

    bool operator == (const Mod_Int &p) const {return x == p.x;}

    bool operator != (const Mod_Int &p) const {return x != p.x;}

    Mod_Int inverse() const {
        assert(*this != Mod_Int(0));
        return pow(mod-2);
    }

    Mod_Int pow(ll k) const{
        Mod_Int now = *this, ret = 1;
        while(k){
            if(k&1) ret *= now;
            now *= now, k >>= 1;
        }
        return ret;
    }

    friend ostream &operator << (ostream &os, const Mod_Int &p){
        return os << p.x;
    }

    friend istream &operator >> (istream &is, Mod_Int &p){
        ll a;
        is >> a;
        p = Mod_Int<mod>(a);
        return is;
    }
};

using mint = Mod_Int<MOD>;

template<typename Monoid>
struct Segment_Tree{
    vector<Monoid> seg;
    const Monoid e;
    const int n;

    Monoid f(const Monoid &a, const Monoid &b) const {return a + b;}
    
    Segment_Tree(int N, const Monoid &e) : e(e), n(1<<(32-__builtin_clz(N-1))){
        seg.assign(2*n, e);
    }
    
    void change(int i, const Monoid &x){
        seg[i += n] = x;
        while(i > 0){
            i /= 2;
            seg[i] = f(seg[2*i], seg[2*i+1]);
        }
    }

    Monoid query(int a, int b, int i, int l, int r) const{
        if(a >= r || b <= l) return e;
        if(a <= l && r <= b) return seg[i];
        Monoid vl = query(a, b, 2*i, l, (l+r)/2);
        Monoid vr = query(a, b, 2*i+1, (l+r)/2, r);
        return f(vl, vr);
    }

    Monoid query(int a, int b) {return query(a, b, 1, 0, n);}

    bool check(const Monoid &a, const Monoid & b) const {return a <= b;}

    int find_first(int a, int b, const Monoid &x, int i, int l, int r) const{
        if(a >= b || a >= r || b <= l || !check(seg[i], x)) return -1;
        if(r-l == 1) return l;
        int m = (l+r)/2;
        if(b <= m) return find_first(a, b, x, 2*i, l, m);
        if(a >= m) return find_first(a, b, x, 2*i+1, m, r);
        int tmp = find_first(a, m, x, 2*i, l, m);
        return (tmp == -1? find_first(m, b, x, 2*i+1, m, r) : tmp);
    }

    int find_first(int a, int b, const Monoid &x) const {return find_first(a, b, x, 1, 0, n);}

    int find_last(int a, int b, const Monoid &x, int i, int l, int r) const{
        if(a >= b || a >= r || b <= l || !check(seg[i], x)) return -1;
        if(r-l == 1) return l;
        int m = (l+r)/2;
        if(b <= m) return find_last(a, b, x, 2*i, l, m);
        if(a >= m) return find_last(a, b, x, 2*i+1, m, r);
        int tmp = find_last(m, b, x, 2*i+1, m, r);
        return (tmp == -1? find_last(a, m, x, 2*i, l, m) : tmp);
    }

    int find_last(int a, int b, const Monoid &x) const {return find_last(a, b, x, 1, 0, n);}

    Monoid operator [] (int i) const {return seg[n+i];}
    
    void clear(){
        fill(all(seg), e);
    }
};

int main(){
    int N, K;
    cin >> N >> K;
    int p[N];
    rep(i, N){
        int x; cin >> x; x--;
        p[x] = i;
    }
    Segment_Tree<mint> seg1(N, 0), seg2(N, 0);
    mint r = mint(K-1)/mint(K);
    mint pw[N];
    rep(i, N){
        if(i < K) pw[i] = 1;
        else pw[i] = pw[i-1]*r;
        seg1.change(i, 0), seg2.change(i, pw[i]);
    }
    mint ans = 0;
    rep(i, N){
        int j = p[i];
        ans += seg1.query(j+1, N)*2;
        ans += seg2.query(j+1, N)/pw[j];
        seg1.change(j, 1), seg2.change(j, -seg2.query(j, j+1));
    }
    cout << ans/2 << endl;
}
### 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 <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
//const int MOD = 1000000007;
const int MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const double pi = acos(-1.0);
const double EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

template<int mod>
struct Mod_Int{
    ll x;

    Mod_Int() : x(0) {}

    Mod_Int(ll y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    Mod_Int &operator += (const Mod_Int &p){
        x = (x + p.x) % mod;
        return *this;
    }

    Mod_Int &operator -= (const Mod_Int &p){
        x = (x + mod - p.x) % mod;
        return *this;
    }

    Mod_Int &operator *= (const Mod_Int &p){
        x = (x * p.x) % mod;
        return *this;
    }

    Mod_Int &operator /= (const Mod_Int &p){
        *this *= p.inverse();
        return *this;
    }

    Mod_Int &operator ++ () {return *this += Mod_Int(1);}

    Mod_Int operator ++ (int){
        Mod_Int tmp = *this;
        ++*this;
        return tmp;
    }

    Mod_Int &operator -- () {return *this -= Mod_Int(1);}

    Mod_Int operator -- (int){
        Mod_Int tmp = *this;
        --*this;
        return tmp;
    }

    Mod_Int operator - () const {return Mod_Int(-x);}

    Mod_Int operator + (const Mod_Int &p) const {return Mod_Int(*this) += p;}

    Mod_Int operator - (const Mod_Int &p) const {return Mod_Int(*this) -= p;}

    Mod_Int operator * (const Mod_Int &p) const {return Mod_Int(*this) *= p;}

    Mod_Int operator / (const Mod_Int &p) const {return Mod_Int(*this) /= p;}

    bool operator == (const Mod_Int &p) const {return x == p.x;}

    bool operator != (const Mod_Int &p) const {return x != p.x;}

    Mod_Int inverse() const {
        assert(*this != Mod_Int(0));
        return pow(mod-2);
    }

    Mod_Int pow(ll k) const{
        Mod_Int now = *this, ret = 1;
        while(k){
            if(k&1) ret *= now;
            now *= now, k >>= 1;
        }
        return ret;
    }

    friend ostream &operator << (ostream &os, const Mod_Int &p){
        return os << p.x;
    }

    friend istream &operator >> (istream &is, Mod_Int &p){
        ll a;
        is >> a;
        p = Mod_Int<mod>(a);
        return is;
    }
};

using mint = Mod_Int<MOD>;

template<typename Monoid>
struct Segment_Tree{
    vector<Monoid> seg;
    const Monoid e;
    const int n;

    Monoid f(const Monoid &a, const Monoid &b) const {return a + b;}
    
    Segment_Tree(int N, const Monoid &e) : e(e), n(1<<(32-__builtin_clz(N-1))){
        seg.assign(2*n, e);
    }
    
    void change(int i, const Monoid &x){
        seg[i += n] = x;
        while(i > 0){
            i /= 2;
            seg[i] = f(seg[2*i], seg[2*i+1]);
        }
    }

    Monoid query(int a, int b, int i, int l, int r) const{
        if(a >= r || b <= l) return e;
        if(a <= l && r <= b) return seg[i];
        Monoid vl = query(a, b, 2*i, l, (l+r)/2);
        Monoid vr = query(a, b, 2*i+1, (l+r)/2, r);
        return f(vl, vr);
    }

    Monoid query(int a, int b) {return query(a, b, 1, 0, n);}

    bool check(const Monoid &a, const Monoid & b) const {return a <= b;}

    int find_first(int a, int b, const Monoid &x, int i, int l, int r) const{
        if(a >= b || a >= r || b <= l || !check(seg[i], x)) return -1;
        if(r-l == 1) return l;
        int m = (l+r)/2;
        if(b <= m) return find_first(a, b, x, 2*i, l, m);
        if(a >= m) return find_first(a, b, x, 2*i+1, m, r);
        int tmp = find_first(a, m, x, 2*i, l, m);
        return (tmp == -1? find_first(m, b, x, 2*i+1, m, r) : tmp);
    }

    int find_first(int a, int b, const Monoid &x) const {return find_first(a, b, x, 1, 0, n);}

    int find_last(int a, int b, const Monoid &x, int i, int l, int r) const{
        if(a >= b || a >= r || b <= l || !check(seg[i], x)) return -1;
        if(r-l == 1) return l;
        int m = (l+r)/2;
        if(b <= m) return find_last(a, b, x, 2*i, l, m);
        if(a >= m) return find_last(a, b, x, 2*i+1, m, r);
        int tmp = find_last(m, b, x, 2*i+1, m, r);
        return (tmp == -1? find_last(a, m, x, 2*i, l, m) : tmp);
    }

    int find_last(int a, int b, const Monoid &x) const {return find_last(a, b, x, 1, 0, n);}

    Monoid operator [] (int i) const {return seg[n+i];}
    
    void clear(){
        fill(all(seg), e);
    }
};

int main(){
    int N, K;
    cin >> N >> K;
    int p[N];
    rep(i, N){
        int x; cin >> x; x--;
        p[x] = i;
    }
    Segment_Tree<mint> seg1(N, 0), seg2(N, 0);
    mint r = mint(K-1)/mint(K);
    mint pw[N];
    rep(i, N){
        if(i < K) pw[i] = 1;
        else pw[i] = pw[i-1]*r;
        seg1.change(i, 0), seg2.change(i, pw[i]);
    }
    mint ans = 0;
    rep(i, N){
        int j = p[i];
        ans += seg1.query(j+1, N)*2;
        ans += seg2.query(j+1, N)/pw[j];
        seg1.change(j, 1), seg2.change(j, -seg2.query(j, j+1));
    }
    cout << ans/2 << endl;
}
```