#include "bits/stdc++.h"

using namespace std;
using lint = int64_t;
int n, m;
int lo, hi;
int mod = (1<<30);

struct segtree{
    vector<lint> s, lazy;
    vector<int>lid, rid;
    int create(){
        int id = int(s.size());
        s.push_back(0);
        lazy.push_back(0);
        lid.push_back(-1);
        rid.push_back(-1);
        return id;   
    }
    segtree(int n) {
        s.reserve(30 * n);
        lazy.reserve(30 * n);
        lid.reserve(30 * n);
        rid.reserve(30 * n);
        create();
    }
    void push(int v, int l, int r){
        assert(v < lid.size() and v < rid.size());
        assert(v < lid.size() and v < rid.size());
        s[v] += (r - l + 1) * lazy[v];
        s[v] %= mod;
        if(l != r) {
            if(lid[v] == -1) lid[v] = create();
            if(rid[v] == -1) rid[v] = create();
            lazy[lid[v]] += lazy[v];
            lazy[lid[v]] %= mod;
            lazy[rid[v]] += lazy[v];
            lazy[rid[v]] %= mod;
        }
        lazy[v] = 0;
    }

    void update(int v, int l, int r, int a, int b, lint x){
        assert(v >= 0 and v < s.size());
        if(a <= l && r <= b){
            lazy[v] += x;
            lazy[v] %= mod;
            push(v, l, r);
            return;
        }
        if(r < a || l > b) return;
        int m = (l + r) >> 1;
        push(v, l, r);
        update(lid[v], l, m, a, b, x);
        update(rid[v], m + 1, r, a, b, x);
        s[v] = s[lid[v]] + s[rid[v]];
        s[v] %= mod;
    }
    lint query(int v, int l, int r, int a, int b){
        push(v, l, r);
        if(a <= l && r <= b) return s[v];
        if(r < a || l > b) return 0;
        int m = (l + r) >> 1;
        return (query(lid[v], l, m, a, b) + query(rid[v], m+1, r, a, b)) % mod;
    }


};

int main() {
    cin>>n>>m;
    lo = 0, hi = (1<<m) - 1;
    segtree seg(n);
    lint x = 0;
    for(int i=1;i<=n;i++){
        int p, q, md = (1 << m);
        cin>>p>>q;
        p = (p + x) % md;
        q = (q + x) % md;
        int l = min(p, q), r = max(p, q);
        seg.update(0, lo, hi, l, r, i);
        x = (x + seg.query(0, lo, hi, l, r)) % mod;
        // cout<<i<<" "<<x<<"\n";
    }
    cout<<x<<"\n";
    return 0;
}