#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10, M = 4e5;
ll n, m, q;
struct node
{
	ll v, sex, f, id;
} e[N], e1[N];
bool cmp2(node a, node b)
{
	return a.v > b.v;
}
#define MAXN 10000005
ll a[MAXN], p[MAXN];
ll p1 = 1000000009, p2 = 998244353, p3 = 1000000007;
ll qim(ll a, ll b, ll p)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
		{
			res = res * a % p;
		}
		a = a * a % p;
		b >>= 1;
	}

	return res;
}
void solve1()
{
	cin >> n >> a[0];

	for (int i = 1; i <= n; i++)
	{
		p[i] = i;
	}
	for (int i = 1; i <= n; i++)
	{
		a[i] = (a[i - 1] * p2 % p1 + p3) % p1;
		swap(p[i], p[a[i] % i + 1]);
		// cout << p[i] << endl;
	}

	ll res = 0, mid = 0;
	priority_queue<ll> qmax;
	priority_queue<ll, vector<ll>, greater<ll>> qmin;
	qmax.push(p[1]);
	mid = p[1];
	res = mid * qim(19, 1, p2) % p2;
	for (int i = 2; i <= n; i++)
	{
		if (p[i] > mid)
		{
			if (i % 2 == 1)
			{
				int maxx = qmin.top();
				if (maxx >= p[i])
				{
					mid = p[i];
				}
				else
				{
					mid = maxx;
					qmin.pop();
					qmin.push(p[i]);
				}
				qmax.push(mid);
			}
			else
			{
				qmin.push(p[i]);
			}
		}
		else
		{
			if (i % 2 == 1)
			{
				qmax.push(p[i]);
			}
			else
			{
				qmax.pop();
				qmin.push(mid);

				qmax.push(p[i]);
				mid = qmax.top();
			}
		}


		res = (res + mid * qim(19, i, p2) % p2) % p2;
	}

	cout << res << endl;
}
void solve()
{

	/*cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
	{
		cin >> e[i].v >> e[i].sex;
		e[i].id = i;
	}
	ll maxx = -1, f = -1;
	for (int i = 1; i <= n; i++)
	{
		e1[i].sex = e[i].sex;
		e1[i].v = e[i].v;
		e1[i].id = e[i].id;
		e1[i].f = 0;
		e[i].f = 0;
		if (e1[i].sex == 1)
		{
			maxx = max(maxx, e1[i].v);
			f = i;
		}
	}
	if (maxx == -1)
	{
		sort(e1 + 1, e1 + n + 1, cmp2);
		for (int i = 1; i <= m; i++)
		{
			e[e1[i].id].f = 1;
		}
	}
	else
	{
		e[f].f = 1;
		sort(e1 + 1, e1 + n + 1, cmp2);
		for (int i = 1; i <= m - 1; i++)
		{
			e[e1[i].id].f = 1;
		}
	}
	while (q--)
	{
		int op;
		cin >> op;

		if (op == 1)
		{

			int a, b;
			cin >> a >> b;
			e[a].sex = b;
			ll maxx = -1, f = -1;
			for (int i = 1; i <= n; i++)
			{
				e[i].f = 0;
				e1[i].sex = e[i].sex;
				e1[i].v = e[i].v;
				e1[i].id = e[i].id;
				e1[i].f = 0;
				if (e1[i].sex == 1)
				{
					maxx = max(maxx, e1[i].v);
					f = i;
				}
			}
			if (maxx == -1)
			{
				sort(e1 + 1, e1 + n + 1, cmp2);
				for (int i = 1; i <= m; i++)
				{
					e[e1[i].id].f = 1;
				}
			}
			else
			{
				e[f].f = 1;
				sort(e1 + 1, e1 + n + 1, cmp2);
				for (int i = 1; i <= m - 1; i++)
				{
					e[e1[i].id].f = 1;
				}
			}
		}
		else
		{
			int x;
			cin >> x;
			if (e[x].f)
				cout << 1 << endl;
			else
				cout << 0 << endl;
		}
	}*/
}
int main()
{
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	int t = 1;
	// cin >> t;
	while (t--)
		solve1();
	return 0;
}