#include<bits/stdc++.h>
using namespace std;
vector<int>vec[1000005],uu,vv;
vector<pair<int,int> >qry[1000005];
int vis[1000005],dep[1000005],n,q,fa[1000005],ans[1000005];
const int p=998244353;
long long mi[5000006];
void init() { //先初始化
    mi[1]=1;
   for(int i=2;i<=5000000;i++) { 
        mi[i]=mi[i-1]*45254%p;
    }
}
int Rand(int i) { //生成第i个点的父亲
        return mi[i]%(i-1)+1;
}
int RAND(int i,int op) { //生成第i组询问,第j个数
    if(op==1) return mi[i]*12432%n+1;
   else return mi[i]%n+1;
}
int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(x);
}
void tarjan(int u,int father){
	dep[u]=dep[father]+1;
	vis[u]++;
	for(int i=0;i<vec[u].size();i++){
		int v=vec[u][i];
		tarjan(v,u);
		fa[find(v)]=u;
	}
	vis[u]++;
	for(int i=0;i<qry[u].size();i++){
		int v=qry[u][i].first,id=qry[u][i].second;
		if(vis[v]==2&&!ans[id])ans[id]=find(v);
	}
}
int main(){
	init();
	cin>>n>>q;
	for(int i=1;i<n;i++){
		int f=Rand(i+1);
		vec[f].push_back(i+1);
	}
	for(int i=1;i<=q;i++){
		int x1=RAND(i,1),x2=RAND(i,2);
		qry[x1].push_back(make_pair(x2,i));
		qry[x2].push_back(make_pair(x1,i));
		uu.push_back(x1);
		vv.push_back(x2);
	}
	tarjan(1,0);int anss=0;
	for(int i=1;i<=q;i++){
		anss^=dep[uu[i]]+dep[vv[i]]-2*dep[ans[i]];
	}
	cout<<anss;
	return 0;
}