#include <bits/stdc++.h>

using namespace std;

#define int long long

const int P = 998244353;

const int N = 1e7 + 7;

const int mod = 1e9 + 7;

int n;
int a[N];
int p[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> a[0];
	for (int i = 1;i <= n;i++){
		a[i] = (a[i - 1] % (mod + 2) * P % (mod + 2) + mod) % (mod + 2);
		p[i] = i;
	}
	for (int i = 1;i <= n;i++){
		swap(p[i],p[a[i] % i + 1]);
	}
	
	int res = 0;
	int cur = 1;
	// l.b x r.b
	set<int> r;
	set<int,greater<>> l;

	for (int i = 1;i <= n;i++){
		(cur *= 19) % P;
		if (l.empty()){
			l.insert(p[i]);
		}else{
			if (*l.begin() < p[i]){
				r.insert(p[i]);
				if (r.size() - l.size() > 1){
					l.insert(*r.begin());
					r.erase(r.begin());
				}
			}else{
				l.insert(p[i]);
				if (l.size() - r.size() > 1){
					r.insert(*l.begin());
					l.erase(l.begin());
				}
			}
		}
		if (l.size() == r.size()){
			(res += *l.begin() % P * cur % P) %= P;
			//cout << *l.begin() << endl;
		}else{
			if (l.size() > r.size()){
				(res += *l.begin() % P * cur % P) %= P;	
				//cout << *l.begin() << endl;
			}else{
				(res += *r.begin() % P * cur % P) %= P;	
				//cout << *r.begin() << endl;
			}
		}
	}

	cout << res << endl;




	return 0;
}