#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10, mod = 1 << 30;
int n, m, all, tot, root;
mt19937 rnd(time(0));
int val[N], siz[N], tag[N], w[N], sum[N], ch[N][2], b[N];
int tree_siz[N];
int newnode(int x, int s, int l)
{
    x %= mod;
    int ret = ++tot;
    w[ret] = rnd(), b[ret] = l;
    val[ret] = x, siz[ret] = s;
    tree_siz[ret] = s;
    sum[ret] = 1ll * x * s % mod;
    return ret;
}
void pushdown(int cur)
{
    if (int lc = ch[cur][0]; lc)
    {
        tag[lc] = (tag[lc] + tag[cur]) % mod;
        sum[lc] = (sum[lc] + 1ll * tree_siz[lc] * tag[cur] % mod) % mod;
        val[lc] = (val[lc] + tag[cur]) % mod;
    }
    if (int rc = ch[cur][1]; rc)
    {
        tag[rc] = (tag[rc] + tag[cur]) % mod;
        sum[rc] = (sum[rc] + 1ll * tree_siz[rc] * tag[cur] % mod) % mod;
        val[rc] = (val[rc] + tag[cur]) % mod;
    }
    tag[cur] = 0;
}
void pushup(int cur)
{
    tree_siz[cur] = siz[cur] + tree_siz[ch[cur][0]] + tree_siz[ch[cur][1]];
    sum[cur] = 1ll * val[cur] * siz[cur] % mod;
    sum[cur] += (sum[ch[cur][0]] + sum[ch[cur][1]]) % mod;
    sum[cur] %= mod;
}
pair<int, int> split(int x, int z)
{
    if (!x)
        return {0, 0};

    pushdown(x);
    pair<int, int> ret;
    if (z < b[x])
    {
        ret = split(ch[x][0], z);
        ch[x][0] = ret.second;
        ret.second = x;
    }
    else
    {
        ret = split(ch[x][1], z);
        ch[x][1] = ret.first;
        ret.first = x;
    }
    pushup(x);
    return ret;
}
int merge(int x, int y)
{
    if (!x or !y)
        return x | y;

    pushdown(x), pushdown(y);
    int ret;
    if (w[x] < w[y])
    {
        ret = merge(ch[x][1], y);
        ch[x][1] = ret;
        ret = x;
    }
    else
    {
        ret = merge(x, ch[y][0]);
        ch[y][0] = ret;
        ret = y;
    }
    pushup(ret);
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    all = 1 << m;
    root = newnode(0, all, 0);

    int x = 0;
    for (int i = 1, p, q; i <= n; i++)
    {
        cin >> p >> q;
        p = (p + x) % all, q = (q + x) % all;
        if (p > q)
            swap(p, q);

        auto dfs = [&](auto &dfs, int x, int v) -> int
        {
            if (!x)
                return 0;
            pushdown(x);
            if (ch[x][1])
            {
                ch[x][1] = dfs(dfs, ch[x][1], v);
                pushup(x);
                return x;
            }
            if (b[x] + siz[x] == v)
                return x;
            int w_cur = rnd();
            if (w_cur > w[x])
            {
                int cur = ++tot;
                w[cur] = w_cur;
                val[cur] = val[x];
                siz[cur] = siz[x] - (v - b[x]);
                b[cur] = v;

                siz[x] = v - b[x], ch[x][1] = cur;
                pushup(x), pushup(cur);
                return x;
            }
            else
            {
                int cur = ++tot;
                w[cur] = w_cur;
                val[cur] = val[x];
                siz[cur] = siz[x] - (v - b[x]);
                b[cur] = v;

                siz[x] = v - b[x];
                ch[cur][0] = x;
                pushup(x), pushup(cur);
                return cur;
            }
            assert(false);
        };
        auto r1 = split(root, p - 1);
        r1.first = dfs(dfs, r1.first, p);
        root = merge(r1.first, r1.second);
        auto r2 = split(root, q);
        r2.first = dfs(dfs, r2.first, q + 1);
        root = merge(r2.first, r2.second);

        r1 = split(root, p - 1), r2 = split(r1.second, q);
        tag[r2.first] = (tag[r2.first] + i) % mod;
        val[r2.first] = (val[r2.first] + i) % mod;
        sum[r2.first] = (sum[r2.first] + 1ll * i * tree_siz[r2.first] % mod) % mod;
        x = (x + sum[r2.first]) % mod;
        root = merge(r1.first, merge(r2.first, r2.second));
    }

    cout << x << '\n';
}
/*
 5 2
 2 1
 1 3
 3 2
 1 0
 0 2
*/