#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define lc son[now][0]
#define rc son[now][1]
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

const int N = 2000020;

int son[N][2], wt[N], tot, root, L[N], R[N];
unordered_map<int,int> mp;
unsigned val[N], sum[N], add[N], sz[N];

int newNode(unsigned x, int l, int r) {
    tot++;
    R[tot] = r;
    L[tot] = l;
    sz[tot] = r-l+1;
    val[tot] = x;
    sum[tot] = x * (r - l + 1);
    wt[tot] = rand()*rand();
    return tot;
}

void up(int now) {
    sz[now] = sz[lc] + sz[rc] + R[now] - L[now] + 1;
    sum[now] = sum[lc] + sum[rc] + val[now] * (R[now] - L[now] + 1);
}
void down(int now) {
    if (add[now]) {
        if(lc) add[lc] += add[now];
        if(rc) add[rc] += add[now];
        if(lc) val[lc] += add[now];
        if(rc) val[rc] += add[now];
        if(lc) sum[lc] += add[now] * sz[lc];
        if(rc) sum[rc] += add[now] * sz[rc];
        add[now] = 0;
    }
}
int merge(int x, int y) {
    if (!x || !y) return x + y;
    
    if (wt[x] < wt[y]) { down(x);
        son[x][1] = merge(son[x][1], y);
        up(x);
        return x;
    }
    down(y);
    son[y][0] = merge(x, son[y][0]);
    up(y);
    return y;
}



void split(int now, int k, int &x, int &y) {
    if (!now) {
        x = y = 0;
        return;
    }
    down(now);
    if (L[now] <= k) x = now, split(rc, k, rc, y);
    else y = now, split(lc, k, x, lc);
    up(now);
    if (x) up(x);
    if (y) up(y);
}

void duan(int a) {
    int x, y, z, t;
    split(root, a, t, y);
    int now = t;
    down(now);
    while (son[now][1]) now = son[now][1], down(now);
    if (L[now] != a) {
        split(t, L[now]-1, x, z);
        int ss = newNode(val[now], L[now], a-1);
        int tt = newNode(val[now], a, R[now]);
        root = merge(merge(x, merge(ss, tt)), y);
    } else {
        root = merge(t, y);
    }
}

int main() {
    int ttt = time(0);
    srand(ttt);
    
    int n, m; scanf("%d%d", &n, &m);
    unsigned ksj = 0, mod = (1<<m);
    root = newNode(0, 0, mod-1);
    root = merge(root, newNode(0, mod, mod));
    int x, y, z, t;
    rep (i, 1, n) {
        int p, q; scanf("%d%d", &p, &q);
        p = (p + ksj % mod) % mod;
        q = (q + ksj % mod) % mod;
        int l = min(p, q), r = max(p, q);
        if (!mp[l]) duan(l), mp[l]=1;
        if (!mp[r+1]) duan(r+1), mp[r+1] =1;
        split(root, l-1, x, t);
        split(t, r, y, z);
        unsigned u = i;
        up(y);
        add[y] += u;
        val[y] += u;
        sum[y] += u * sz[y];
        ksj += sum[y];
        root = merge(x, merge(y, z));
    }
    cout << (unsigned)(ksj % (1<<30)) <<'\n';
    return 0;
}
/*
5 2
2 1
1 3
3 2
1 0
0 2

*/