#include <bits/stdc++.h>
#define int long long
using namespace std;

const int M = 5e5 + 5;

int n, m, mod = 1 << 30, ans;

int rt, tot, fa[M], son[M][2], cnt[M], sz[M], val[M], a[M], b[M], A[M], B[M];

void clear(int x) {
    fa[x] = son[x][0] = son[x][1] = cnt[x] = sz[x] = val[x] = 0;
}

void pushup(int x) {
    sz[x] = sz[son[x][0]] + sz[son[x][1]] + cnt[x];
    a[x] = (a[son[x][0]] + a[son[x][1]] + A[x]) % mod;
    b[x] = (b[son[x][0]] + b[son[x][1]] + B[x]) % mod;
}

bool get(int x) {
    return x == son[fa[x]][1];
}

void rotate(int x) {
    int y = fa[x];
    int z = fa[y];
    bool c = get(x);
    son[y][c] = son[x][c ^ 1];
    if (son[x][c ^ 1]) {
        fa[son[x][c ^ 1]] = y;
    }
    son[x][c ^ 1] = y;
    fa[y] = x;
    fa[x] = z;
    if (z) {
        son[z][y == son[z][1]] = x;
    }
    pushup(y);
}

void splay(int x, int t) {
    for (int f = fa[x]; f != t; rotate(x), f = fa[x]) {
        if (fa[f] != t) {
            rotate(get(f) == get(x) ? f : x);
        }
    }
    if (t == 0) {
    	rt = x;
    }
    pushup(x);
}

void insert(int k, int v) {
    if (!rt) {
        val[++tot] = k;
        A[tot] = v;
        B[tot] = 1ll * k * v % mod;
        cnt[tot]++;
        rt = tot;
        pushup(rt);
        return;
    }
    int cur = rt, f = 0;
    while (1) {
        if (val[cur] == k) {
            cnt[cur]++;
            A[cur] = (A[cur] + v) % mod;
            B[cur] = (B[cur] + 1ll * k * v % mod) % mod;
            pushup(cur);
            pushup(f);
            splay(cur, 0);
            break;
        }
        f = cur;
        cur = son[cur][k > val[cur]];
        if (!cur) {
            val[++tot] = k;
            cnt[tot]++;
            A[tot] = v;
            B[tot] = 1ll * k * v % mod;
            fa[tot] = f;
            son[f][k > val[f]] = tot;
            pushup(tot);
            pushup(f);
            splay(tot, 0);
            break;
        }
    }
}

int find(int k) {
    int cur = rt;
    while (cur) {
        if (k == val[cur]) {
        	return cur;
        } else if (k < val[cur]) {
        	cur = son[cur][0];
        } else {
        	cur = son[cur][1];
        }
    }
    return cur;
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int l, r;
		cin >> l >> r;
		l = (l + ans) % (1 << m);
		r = (r + ans) % (1 << m);
		if (l > r) {
			swap(l, r);
		}
		insert(l, i);
		if (r + 1 < 1 << m) {
			insert(r + 1, mod - i);
		}
        int u = find(l), v = find(r + 1);
        splay(v, 0);
        splay(u, v);
		ans = (ans + 1ll * (a[u] - a[son[u][0]] + mod) % mod * (r + 1) % mod) % mod;
		ans = (ans - (b[u] - b[son[u][0]] + mod) % mod + mod) % mod;
        ans = (ans + 1ll * a[son[u][0]] * (r - l + 1) % mod) % mod;
	}
	cout << ans << '\n';

	return 0;
}