#include <cstdio>
#include <random>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first 
#define se second 
#define mp(a, b) make_pair(a, b)
#define pr pair <int, int>
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 2e6 + 5;
const int P = (1 << 30); 
int n, m, l, r, ans; 
mt19937 rng(time(NULL)); 

int inc (int a, int b) { return (a += b) >= P ? a - P : a; }
int mul (int a, int b) { return 1ll * a * b % P; }

namespace FHQ {
  #define ls t[p].l 
  #define rs t[p].r
  struct node { int l, r, v, s, sl, sr, sz, num, tga; } t[N]; 
  int rt, cnt; 
  
  void reset (int m) {
    rep(i, 1, cnt) t[i].l = t[i].r = t[i].sl = t[i].sr = t[i].s = t[i].tga = 0; 
    t[rt = cnt = 1] = (node){0, 0, 0, 0, 0, (1 << m) - 1, 1 << m, 1, 0}; 
  }
  void pushup (int p) {
    t[p].num = t[ls].num + t[rs].num + 1; 
    t[p].sz = t[ls].sz + t[rs].sz + t[p].sr - t[p].sl + 1; 
    t[p].s = inc(inc(t[ls].s, t[rs].s), mul(t[p].v, t[p].sr - t[p].sl + 1)); 
  }
  void lazy (int p, int k) {
    t[p].s = inc(t[p].s, mul(t[p].sz, k)); 
    t[p].v = inc(t[p].v, k); 
    t[p].tga = inc(t[p].tga, k); 
  }
  void down (int p) {
    if(t[p].tga) lazy(ls, t[p].tga), lazy(rs, t[p].tga); 
    t[p].tga = 0;  
  }
  pr Split (int p, int k) {
    if(!p) return mp(0, 0); 
    down(p); 
    if(t[p].sl <= k) {
      pr o = Split(rs, k); rs = o.fi; 
      pushup(p); return mp(p, o.se); 
    } else {
      pr o = Split(ls, k); ls = o.se; 
      pushup(p); return mp(o.fi, p); 
    }
  }
  int Merge (int p, int k) {
    if(!p || !k) return p | k; 
    down(p), down(k); 
    if(rng() % (t[p].num + t[k].num) < t[p].num) {
      rs = Merge(rs, k), pushup(p); 
      return p; 
    } else {
      t[k].l = Merge(p, t[k].l), pushup(k); 
      return k; 
    }
  }
  int find (int k) {
    int p = rt, ans = 0; 
    while (p) {
      down(p); 
      if(t[p].sl <= k) ans = p, p = rs;
      else p = ls; 
    }
    return ans; 
  }
  void add (int l) {
    int pl = find(l); 
    if(t[pl].sl != l) {
      pr o1 = Split(rt, t[pl].sl - 1), o2 = Split(o1.se, t[pl].sl);
      t[++cnt] = (node){0, 0, t[pl].v, mul(t[pl].v, l - t[pl].sl), t[pl].sl, l - 1, l - t[pl].sl, 1, 0};
      t[pl].sl = l, t[pl].sz = t[pl].r - l + 1, t[pl].s = mul(t[pl].v, t[pl].sz);
      rt = Merge(o1.fi, cnt);
      rt = Merge(rt, pl); 
      rt = Merge(rt, o2.se);    
    }
  }
  int update (int l, int r, int v) {
    add(l);
    if(r != (1 << m) - 1) add(r + 1);  
    pr o1 = Split(rt, l - 1), o2 = Split(o1.se, r); 
    lazy(o2.fi, v); int ans = t[o2.fi].s; 
    rt = Merge(o1.fi, o2.fi);
    rt = Merge(rt, o2.se); 
    return ans; 
  }
}

int main () {
  ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0); 
  cin >> n >> m; 
  FHQ :: reset(m); 
  rep(i, 1, n) {
    cin >> l >> r; 
    l = (l + ans) % (1 << m), r = (r + ans) % (1 << m); 
    if(l > r) swap(l, r); 
    ans = inc(ans, FHQ :: update(l, r, i)); 
  }
  cout << ans << '\n'; 
  return 0; 
}