#include <bits/stdc++.h>
#define for_(i,a,b) for (int i = (a); i < (b); i++)
#define rep_(i,a,b) for (int i = (a); i <= (b); i++)
#define per_(i,a,b) for (int i = (a); i >= (b); i--)
#define pii pair<int, int>
#define pll pair<ll, ll> 
#define fi first
#define se second
#define ll long long
#define all(v) v.begin(), v.end()
#define clr(x) memset(x, 0, sizeof(x))
#define ull unsigned long long
#define pb push_back
#define DEBUG(x) cerr << #x << '=' << x << endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"]=";rep_(_x,(L),(R))cerr<<a[_x]<<" "; cerr<<endl; 
	#ifdef LOCAL
#define line cout << "--------------------------------" << endl;
#define CE cout << endl;
#define CO cout << "OK" << endl;
#define D DEBUG
    #endif
#define endl '\n'
#define int ll
using namespace std;
mt19937 gen(114514);
const int maxn = 1e6 + 10;
const int mod = 1LL<<30;
int n, m;
struct node {
	int val, sz, fix, a, b, K, B;
	node *ls, *rs;
	node(void){
	}
	node(int _val, node *emp, int _K, int _B) : ls(emp), rs(emp), val(_val), sz(1), fix(gen()), K(_K), B(_B), a(_K), b(_B){}
}*rt, *emp, pool[maxn], *curpool = pool;
node* newnode(int x, int K, int B) {
	node *u = ++curpool;
	*u = node(x, emp, K, B);
	return u;
}
void pushup(node *u) {
	u -> sz = u -> ls -> sz + u -> rs -> sz + 1;
	u -> a = u -> ls -> a + u -> rs -> a + u -> K;
	u -> b = u -> ls -> b + u -> rs -> b + u -> B;
	return;
}
void merge(node *&u, node *l, node *r) {
	if (l == emp) { u = r; return;}
	if (r == emp) { u = l; return;}	
	if (l -> fix > r -> fix) {
		u = l, merge(u -> rs, l -> rs, r);
	} else {
		u = r, merge(u -> ls, l, r -> ls);
	}
	pushup(u);
}
void split_val(node* u, node *&l, node *&r, int x) {
	if (u == emp) {
		l = r = emp;
		return;
	}
	if (u -> val <= x) {
		l = u;
		split_val(u -> rs, l -> rs, r, x);
		pushup(l);
	}
	else {
		r = u;
		split_val(u -> ls, l, r -> ls, x);
		pushup(r);
	}
}
void split_sz(node *u, node *&l, node *&r, int x) {
	if (u == emp) {
		l = r = emp;
		return;
	}
	if (u -> ls -> sz + 1 <= x) {
		l = u;
		split_sz(u -> rs, l -> rs, r, x - u -> ls -> sz - 1);
		pushup(l);
	} 
	else {
		r = u;
		split_sz(u -> ls, l, r -> ls, x);
		pushup(r);
	} 
	
}
void insert(int x, int k, int b) {
	node *l, *r, *mid;
	split_val(rt, l, r, x - 1); // (p, 0) i (0, -pi)
//	line;
//	D(k); D(b);
//	line;
	node *u = newnode(x, k, b);
	merge(rt, l, u);
	merge(rt, rt, r);
}
void dfs(node *u, int cnt = 0) {
	cnt++;
	if (u == emp) return;
	dfs(u -> ls, cnt);
	cout << cnt << ':' << (u -> val) << ' ' << (u -> a) << ' ' << (u -> b) << ' ' << (u -> K) << ' ' << (u -> B) << endl;
	dfs(u -> rs, cnt);
}
int get(int x) {
	node *l, *r, *mid;
	split_val(rt, l, r, x);
	ll tmp = 0; tmp = (l -> a) * x % mod + (l -> b); tmp %= mod;
	merge(rt, l, r);
	return tmp;
}

signed main() {
	#ifdef LOCAL
		freopen("w.in", "r", stdin);
	#endif
	emp = pool;
	emp -> sz = 0; emp -> K = emp -> B = 0;
	emp -> a = emp -> b = 0;
	node *u = newnode(0, 0, 0); 
	rt = newnode(1<<30, 0, 0);  merge(rt, u, rt); 
	cin >> n >> m;
	int x = 0; m = 1ll<<m;
	rep_(i, 1, n) {
		int p, q; cin >> p >> q;
		p = (p + x) % m;
		q = (q + x) % m;
		if (p > q) swap(p, q);
//		D(p);
//		D(q);
		insert(p, i, -(p - 1) * i % mod);
		insert(q + 1, -i, ((p - 1) * i % mod + (q - p + 1) * i % mod) % mod);
	//		dfs(rt);
	//		line;		
	//		get(q);
	//		get(p - 1);
	//		cout << get(q) << endl;
	//		cout << get(p - 1) <<endl; 
		x += get(q) - get(p - 1);
		x %= mod;
//		D(x);
//		line;
	}
	x = (x % mod + mod) % mod;
	cout << x << endl;
	return 0;
}