#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3")
#pragma GCC target("f16c")
#pragma GCC target("fma","avx2")
#pragma GCC target("xop","fma4")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#define _CRT_SECURE_NO_WARNINGS
#include<set>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=2100010;
const int mod=1ll<<30;
int n,m,tot,root,a[N];

struct Node{
	int siz;unsigned sum; //区间长度 区间每一个元素被加了多少
	Node(){}
	Node(int _siz,unsigned _sum):siz(_siz),sum(_sum){}
};

struct fhq{
	int l,r,dat,siz;Node val;unsigned sum,add;
#define l(x) t[x].l
#define r(x) t[x].r
#define add(x) t[x].add
#define sum(x) t[x].sum
#define val(x) t[x].val
#define siz(x) t[x].siz
#define dat(x) t[x].dat
}t[N];

inline int nou(Node x)
{
	val(++tot)=x;dat(tot)=rand();siz(tot)=x.siz;sum(tot)=x.siz*x.sum;
	add(tot)=0;
	return tot;
}
inline void update(int p)
{ 
	siz(p)=siz(l(p))+val(p).siz+siz(r(p));
	sum(p)=val(p).sum*val(p).siz;
	if(l(p))sum(p)+=sum(l(p));
	if(r(p))sum(p)+=sum(r(p));
}
inline void spread(int p)
{
	if(!add(p))return;
	if(l(p))sum(l(p))+=siz(l(p))*add(p),
		add(l(p))+=add(p),
		val(l(p)).sum+=add(p);
	if(r(p))sum(r(p))+=siz(r(p))*add(p),
		add(r(p))+=add(p),
		val(r(p)).sum+=add(p);
	add(p)=0;
}

inline void split(int p,int &x,int &y,int v)
{
	if(!p)return x=y=0,void();
	spread(p);
	if(siz(l(p))+1ll*val(p).siz<=v)
		x=p,split(r(p),r(p),y,v-siz(l(p))-val(p).siz);
	else if(siz(l(p))>=v)
		y=p,split(l(p),x,l(p),v);
	else
	{
		v-=siz(l(p)); 
		Node tem=val(p);
		x=p,y=++tot;val(p).siz=v;
		val(y).siz=1ll*tem.siz-v;
		val(y).sum=val(p).sum;
		siz(x)=val(x).siz;
		siz(y)=val(y).siz;
		//dat(y)=dat(x);
		dat(y)=rand();
		sum(x)=val(x).siz*val(x).sum;
		sum(y)=val(y).siz*val(y).sum;
		add(x)=add(y)=0;
		l(y)=0;r(y)=r(x);
		r(x)=0;
		update(x),update(y);
		return;
	}
	update(p);
}

inline int merge(int x,int y)
{
	if(!x||!y)return x^y;
	if(dat(x)<dat(y))
		return spread(x),r(x)=merge(r(x),y),update(x),x;
	else return spread(y),l(y)=merge(x,l(y)),update(y),y;
}

inline unsigned change(int p,int q,unsigned v)
{
	int x,y,z;unsigned res=0;
	split(root,x,y,p-1);
	split(y,y,z,q-p+1);
	add(y)+=v;
	sum(y)+=siz(y)*v;
	val(y).sum+=v;
	res=sum(y);
	root=merge(merge(x,y),z);
	return res;
}

inline int g()
{
	register int res=0;
	char ch;
	while(!isdigit(ch=getchar()));
	do res=res*10+(ch^'0');
	while(isdigit(ch=getchar()));
	return res;
}

inline void out(int x)
{
	if(x>9)out(x/10);
	putchar(x%10+'0');
}

signed main()
{
	srand(time(0)+32213);
	srand(rand());
	n=g(),m=g();
	root=merge(root,nou(Node(1ll<<m,0)));
	unsigned ans=0,m2=1ll<<m;
	int p,q;
	for(int _=1;_<=n;_++)
	{
		p=g(),q=g();
		p=(p+ans)%m2+1,q=(q+ans)%m2+1;
		if(p>q)swap(p,q);
		ans=(ans+change(p,q,1u*_))%mod;
		//printf("%lld\n",ans);
	}
	out(1*ans%mod);
	putchar('\n');
	return 0;
}