#include<bits/stdc++.h>
using namespace std;
#define I inline int
#define V inline void
#define ll long long int
#define isnum(ch) ('0'<=ch&&ch<='9')
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define gc (_op==_ed&&(_ed=(_op=_buf)+fread(_buf,1,100000,stdin),_op==_ed)?EOF:*_op++)
char _buf[100000],*_op(_buf),*_ed(_buf);
I getint(){
	int _s=0;char _ch=gc;
	while(!isnum(_ch))_ch=gc;
	while(isnum(_ch))_s=_s*10+_ch-48,_ch=gc;
	return _s;
}
const int N=5e5,mod=998244353;
int n,m,rt,tot,ans,bas;
int mid[N],len[N],ls[N],rs[N],f[N],s[N],g[N],h[N];
V check(int&x){x-=mod,x+=x>>31&mod;}
I calc(int x){return 1ll*x*(x+1)/2%mod;}
I calc(int l,int r){return(calc(r)+mod-calc(l-1))%mod;}
I Pow(ll t,int x,ll s=1){for(;x;x>>=1,t=t*t%mod)if(x&1)s=s*t%mod;return s;}
#define lc ls[p]
#define rc rs[p]
#define root rt,1,n
#define lson lc,L,mid[p]
#define rson rc,mid[p]+1,R
#define mul(a,b,c){\
		FOR(i,0,2)FOR(j,0,2)FOR(k,0,2)tmp[i][j]+=1ll*a[i][k]*b[k][j];\
		FOR(i,0,2)FOR(j,0,2)c[i][j]=tmp[i][j]%mod,tmp[i][j]=0;}
V init(int&p,int L,int R){
	if(len[p=++tot]=R-L+1,L==R)return;
	mid[p]=getint(),init(lson),init(rson);
}
V work(int p,int L,int R,int fa=0){
	static ll tmp[3][3],S[3][3],T[3][3];
	h[p]=1ll*(calc(L-1)+calc(n-R))*bas%mod;
	f[p]=(1ll*L*(n+1-R)%mod*bas+mod-s[fa])%mod,check(s[p]=s[fa]+f[p]);
	ll p1=f[p],p2=s[fa],p3=g[p],p4=(1ll*(R-L)*(n-R+L-1)+calc(R-L+1)-1)%mod*bas%mod,p5=h[fa];
	FOR(i,0,2)FOR(j,0,2)S[i][j]=i==j;
	T[0][0]=(p3+p4+p5)%mod,T[0][1]=p2,T[0][2]=p1;
	T[1][0]=p4,T[1][1]=(p2+p5)%mod,T[1][2]=(p1+p3)%mod;
	T[2][0]=p4,T[2][1]=0,T[2][2]=(p1+p2+p3+p5)%mod;
	for(int x=m;x;x>>=1){if(x&1)mul(S,T,S);mul(T,T,T);}
	if(check(ans+=S[0][2]),L==R)return;
	g[lc]=(1ll*(R-mid[p])*(n-R)+calc(R-mid[p]))%mod*bas%mod;
	g[rc]=(1ll*(mid[p]-L+1)*(L-1)+calc(mid[p]-L+1))%mod*bas%mod;
	work(lson,p),work(rson,p);
}
int main(){
	n=getint(),m=getint(),bas=Pow(calc(n),mod-2);
	init(root),work(root),cout<<ans;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define I inline int
#define V inline void
#define ll long long int
#define isnum(ch) ('0'<=ch&&ch<='9')
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define gc (_op==_ed&&(_ed=(_op=_buf)+fread(_buf,1,100000,stdin),_op==_ed)?EOF:*_op++)
char _buf[100000],*_op(_buf),*_ed(_buf);
I getint(){
	int _s=0;char _ch=gc;
	while(!isnum(_ch))_ch=gc;
	while(isnum(_ch))_s=_s*10+_ch-48,_ch=gc;
	return _s;
}
const int N=5e5,mod=998244353;
int n,m,rt,tot,ans,bas;
int mid[N],len[N],ls[N],rs[N],f[N],s[N],g[N],h[N];
V check(int&x){x-=mod,x+=x>>31&mod;}
I calc(int x){return 1ll*x*(x+1)/2%mod;}
I calc(int l,int r){return(calc(r)+mod-calc(l-1))%mod;}
I Pow(ll t,int x,ll s=1){for(;x;x>>=1,t=t*t%mod)if(x&1)s=s*t%mod;return s;}
#define lc ls[p]
#define rc rs[p]
#define root rt,1,n
#define lson lc,L,mid[p]
#define rson rc,mid[p]+1,R
#define mul(a,b,c){\
		FOR(i,0,2)FOR(j,0,2)FOR(k,0,2)tmp[i][j]+=1ll*a[i][k]*b[k][j];\
		FOR(i,0,2)FOR(j,0,2)c[i][j]=tmp[i][j]%mod,tmp[i][j]=0;}
V init(int&p,int L,int R){
	if(len[p=++tot]=R-L+1,L==R)return;
	mid[p]=getint(),init(lson),init(rson);
}
V work(int p,int L,int R,int fa=0){
	static ll tmp[3][3],S[3][3],T[3][3];
	h[p]=1ll*(calc(L-1)+calc(n-R))*bas%mod;
	f[p]=(1ll*L*(n+1-R)%mod*bas+mod-s[fa])%mod,check(s[p]=s[fa]+f[p]);
	ll p1=f[p],p2=s[fa],p3=g[p],p4=(1ll*(R-L)*(n-R+L-1)+calc(R-L+1)-1)%mod*bas%mod,p5=h[fa];
	FOR(i,0,2)FOR(j,0,2)S[i][j]=i==j;
	T[0][0]=(p3+p4+p5)%mod,T[0][1]=p2,T[0][2]=p1;
	T[1][0]=p4,T[1][1]=(p2+p5)%mod,T[1][2]=(p1+p3)%mod;
	T[2][0]=p4,T[2][1]=0,T[2][2]=(p1+p2+p3+p5)%mod;
	for(int x=m;x;x>>=1){if(x&1)mul(S,T,S);mul(T,T,T);}
	if(check(ans+=S[0][2]),L==R)return;
	g[lc]=(1ll*(R-mid[p])*(n-R)+calc(R-mid[p]))%mod*bas%mod;
	g[rc]=(1ll*(mid[p]-L+1)*(L-1)+calc(mid[p]-L+1))%mod*bas%mod;
	work(lson,p),work(rson,p);
}
int main(){
	n=getint(),m=getint(),bas=Pow(calc(n),mod-2);
	init(root),work(root),cout<<ans;
	return 0;
}