#include<bits/stdc++.h>
using namespace std;

#define ONLINE
#ifndef ONLINE
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) ;
#endif

using LL=long long;
using PII=pair<int,int>;

template<typename T>
inline T READ(){
	T x=0; bool f=0; char c=getchar();
	while(c<'0' || c>'9') f|=(c=='-'),c=getchar();
	while(c>='0' && c<='9') x=x*10+c-'0',c=getchar();
	return f?-x:x;
}
inline int read(){return READ<int>();}
inline LL readLL(){return READ<LL>();}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int _1e9=1e9;
const int mod=998244353;
LL ksm19(LL b){
	LL ret=1,a=19;
	while(b){
		if(b&1) ret=ret*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ret;
}

#define N 10000010
#define pre first
#define nxt second
PII b[N];
LL a[N];
int n,p[N];

int main(){
	n=read(),a[0]=read();
	for(int i=1;i<=n;i++){
		a[i]=(a[i-1]*998244353+_1e9+7)%(_1e9+9);
		p[i]=i;
	}
	for(int i=1;i<=n;i++){
		swap(p[i],p[(a[i]%i)+1]);
	}
	for(int i=1;i<=n;i++){
		debug("p[%d]=%d\n",i,p[i]);
	}
	for(int i=1;i<n;i++){
		b[i].nxt=i+1;
		b[i+1].pre=i;
	}
	for(int i=1;i<=n;i++){
		debug("%d|pre=%d nxt=%d\n",i,b[i].pre,b[i].nxt);
	}
	int mid=1,cnt=1;
	for(;cnt<(n+1)/2;++cnt){
		mid=b[mid].nxt;
	}
	LL mul=ksm19(n),inv=ksm19(mod-2),ans=0;
	for(int i=n;i>0;i--){
		debug("%d|%d %d\n",i,mid,cnt);
		ans=(ans+mul*mid)%mod;
		if(p[i]<mid) cnt--;
		else if(p[i]==mid){
			if(b[p[i]].pre){
				mid=b[p[i]].pre;
				cnt--;
			}
			else{
				mid=b[p[i]].nxt;
			}
		}
		if(b[p[i]].nxt){
			b[b[p[i]].nxt].pre=b[p[i]].pre;
		}
		if(b[p[i]].pre){
			b[b[p[i]].pre].nxt=b[p[i]].nxt;
		}
		for(;cnt<i/2;++cnt){
			mid=b[mid].nxt;
		}
		for(;cnt>i/2;--cnt){
			mid=b[mid].pre;
		}
		mul=mul*inv%mod;
	}
	printf("%lld\n",ans);
	return 0;
}

/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/