#include <bits/stdc++.h>

using namespace std;

const int N = 4100010;

using i64 = long long;

const int mod = 1 << 30;

struct Node{
    int l, r, key;
    unsigned add, sum, val, sz, self;
} tr[N];
int n, m;
int root, idx;
int p, q, s;

int new_node(unsigned val, unsigned self) {
    int u = ++idx; 
    tr[u].key = rand();
    tr[u].val = val;
    tr[u].self = self;
    tr[u].sum = val * self;
    return u;
}

void pushadd(int u, unsigned v) {
    tr[u].val += v;
    tr[u].add += v;
    tr[u].sum += v * tr[u].sz;    
}

void pushdown(int u) {
    if (tr[u].add) {
        pushadd(tr[u].l, tr[u].add);
        pushadd(tr[u].r, tr[u].add);
        tr[u].add = 0;
    }
}

void pushup(int u) {
    tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum + tr[u].self * tr[u].val;
    tr[u].sz = tr[tr[u].l].sz + tr[tr[u].r].sz + tr[u].self;
}

void split(int u, int k, int &x, int &y) {
    if (!u) return x = y = 0, void();
    pushdown(u);
    if (tr[tr[u].l].sz < k) {
        if (tr[tr[u].l].sz + tr[u].self >= k) {
            int lsz = k - tr[tr[u].l].sz, rsz = tr[u].self - lsz;
            if (rsz) {
                x = new_node(tr[u].val, lsz), tr[x].l = tr[u].l;
                y = new_node(tr[u].val, rsz), tr[y].r = tr[u].r;
            } else {
                x = u, y = tr[u].r;
                tr[x].r = 0;
            } 
            pushup(x), pushup(y);
            return;
        } else {
            x = u;
            split(tr[u].r, k - tr[tr[u].l].sz - tr[u].self, tr[u].r, y);
        }
    } else {
        y = u;
        split(tr[u].l, k, x, tr[u].l);
    }
    pushup(u);
}

int merge(int x, int y) {
    if (!x || !y) return x | y;    
    if (tr[x].key < tr[y].key) {
        pushdown(x);
        tr[x].r = merge(tr[x].r, y);
        return pushup(x), x;
    } else {
        pushdown(y);
        tr[y].l = merge(x, tr[y].l);
        return pushup(y), y;
    }
    assert(false);
    return 0;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    int M = 1 << m;
    root = idx = 1;
    tr[1].self = M, pushup(1);
    unsigned x = 0;
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        (l += x) %= M, (r += x) %= M;
        ++l, ++r;
        if (l > r) swap(l, r);
        split(root, l - 1, p, q);
        split(q, r - l + 1, q, s);
        pushadd(q, i);
        (x += tr[q].sum) %= (1 << 30);
        root = merge(merge(p, q), s);
    }
    cout << x << '\n';
    return 0;
}