#include "bits/stdc++.h"
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct LazySegTree {
	int n;
	vector<uint32_t> t;
	vector<uint32_t> lz;

	uint32_t comb(uint32_t a, uint32_t b) {
		return a + b;
	}
	void push(int node, int l, int r) {
		t[node] += uint32_t(1ULL*(r-l+1)*lz[node]);
		if (l != r) {
			rep(it, 0, 2) {
				lz[2*node + it] += lz[node];
			}
		}
		lz[node] = 0;
	}
	void pull(int node) {
		t[node] = comb(t[2*node], t[2*node+1]);
	}
	LazySegTree(int _n): n(_n) {
		t.resize(2*n, 0);
		lz.resize(2*n, 0);
	}

	void apply(int l, int r, uint32_t val, int node, int tl, int tr) {
		push(node, tl, tr);
		if (r < tl || tr < l) return;
		if (l <= tl && tr <= r) {
			lz[node] = val;
			push(node, tl, tr);
			return;
		}
		int tm = (tl + tr)/2;
		apply(l, r, val, 2*node, tl, tm);
		apply(l, r, val, 2*node+1, tm+1, tr);
		pull(node);
	}
	
	uint32_t query(int l, int r, int node, int tl, int tr) {
		push(node, tl, tr);
		if (r < tl || tr < l) return 0;
		if (l <= tl && tr <= r) return t[node];
		int tm = (tl + tr)/2;
		return query(l, r, 2*node, tl, tm) + query(l, r, 2*node+1, tm+1, tr);
	}

	void apply(int l, int r, int val) {
		assert(l <= r);
		apply(l, r, val, 1, 0, n-1);
	}
	uint32_t query(int l, int r) {
		assert(l <= r);
		return query(l, r, 1, 0, n-1);
	}
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  const int MASK = (1<<30) - 1;
  const int ST = 1<<22;
  int n, m;
  cin >> n >> m;
  int mod_mask = (1<<m)-1;
  map<int, map<int, int>> blocks;
  int block_size = max((1<<m)/ST, 1);
  LazySegTree T(ST);
  uint32_t accum = 0;

  auto add_range = [&](int block, int l, int r, uint32_t val) {
	  uint32_t add = 1ULL*val*(r-l+1);
	  T.apply(block, block, add);

	  auto it = blocks.try_emplace(block).first;
	  auto& mp = it->second;
	  mp[l] += val;
	  if (r+1 < block_size)
		  mp[r+1] -= val;
  };

  auto process_block = [&](int block, int l, int r) {
	  accum += T.query(block, block);

	  auto it = blocks.find(block);
	  if (it == blocks.end()) return;
	  auto& mp = it->second;
	  uint32_t p = 0;
	  rep(i, 0, block_size) {
		  auto it = mp.find(i);
		  if (it != mp.end()) {
			  p += it->second;
		  }
		  if (i >= l && i <= r) {
			  accum += p;
		  }
		  accum -= p;
	  }
  };

  rep(i, 1, n+1) {
	  int l, r;
	  cin >> l >> r;
	  l = (l + accum)&mod_mask;
	  r = (r + accum)&mod_mask;
	  if (l > r) swap(l, r);
	  // cout << l << " " << r << " " << accum << '\n';

	  if ((1<<m) < ST) {
		  // Block size is always 1.
		  T.apply(l, r, i);
		  accum += T.query(l, r);
		  continue;
	  } 

	  int lblock = l/block_size, rblock = r/block_size;
	  int lidx = l%block_size, ridx=  r%block_size;

	  // Handle the edge case where they are in the same block.
	  if (lblock == rblock) {
		  add_range(lblock, lidx, ridx, i);
		  process_block(lblock, lidx, ridx);
		  continue;
	  }

	  // Handle edge blocks
	  add_range(lblock, lidx, block_size - 1, i);
	  add_range(rblock, 0, ridx, i);
	  process_block(lblock, lidx, block_size - 1);
	  process_block(rblock, 0, ridx);
	  lblock++;
	  rblock--;

	  // Handle mid-blocks
	  if (lblock <= rblock) {
		  uint32_t add = uint32_t(1ULL*block_size*i);
		  T.apply(lblock, rblock, add);
		  accum += T.query(lblock, rblock);
	  }
  }
  cout << (accum&MASK) << '\n';
}