#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <sstream>
#include <tuple>
#include <vector>
using namespace std;
using namespace chrono;
#ifdef DEBUG
//#define LOCAL_INPUT_FILE
#else
//#define USE_FILE_IO
#endif
#ifdef USE_FILE_IO
#define INPUT_FILE "input.txt"
#define OUTPUT_FILE "output.txt"
#define cin ____cin
#define cout ____cout
ifstream cin(INPUT_FILE);
ofstream cout(OUTPUT_FILE);
#else
#ifdef LOCAL_INPUT_FILE
#define cin ____cin
ifstream cin("input.txt");
#endif
#endif
const int infinity = (int)1e9 + 42;
const int64_t llInfinity = (int64_t)1e18 + 256;
const int module = (int)1e9 + 7;
const long double eps = 1e-8;
mt19937_64 randGen(system_clock().now().time_since_epoch().count());
inline void raiseError(string errorCode) {
cerr << "Error : " << errorCode << endl;
exit(42);
}
inline int64_t gilbertOrder(int x, int y, int pow, int rotate) {
if (pow == 0) {
return 0;
}
int hpow = 1 << (pow-1);
int seg = (x < hpow) ? (
(y < hpow) ? 0 : 3
) : (
(y < hpow) ? 1 : 2
);
seg = (seg + rotate) & 3;
const int rotateDelta[4] = {3, 0, 0, 1};
int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
int nrot = (rotate + rotateDelta[seg]) & 3;
int64_t subSquareSize = int64_t(1) << (2*pow - 2);
int64_t ans = seg * subSquareSize;
int64_t add = gilbertOrder(nx, ny, pow-1, nrot);
ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
return ans;
}
struct Query {
int l, r, idx;
int64_t ord;
inline void calcOrder() {
ord = gilbertOrder(l, r, 21, 0);
}
};
inline bool operator<(const Query &a, const Query &b) {
return a.ord < b.ord;
}
signed main() {
#ifndef USE_FILE_IO
ios_base::sync_with_stdio(false);
#endif
mt19937 rnd(42);
int n, m, k; cin >> n >> m; k = rnd() % 1048576;
vector<int> p(n+1);
for (int i = 0; i < n; i++) {
int val = rnd() % 1048576;
p[i+1] = p[i] ^ val;
}
vector<Query> qry(m);
for (int i = 0; i < m; i++) {
int l = rnd() % n + 1, r = rnd() % n + 1;
if (l > r) {
swap(l, r);
}
qry[i].l = l; qry[i].r = r;
qry[i].idx = i;
qry[i].calcOrder();
}
int64_t ans = 0;
vector<int64_t> res(m);
vector<int64_t> cnt((int)2e6, 0);
sort(qry.begin(), qry.end());
int l = 0, r = 1;
ans = (p[1] == k);
cnt[p[0]]++; cnt[p[1]]++;
for (Query q: qry) {
while (l > q.l) {
l--;
ans += cnt[p[l] ^ k];
cnt[p[l]]++;
}
while (r < q.r) {
r++;
ans += cnt[p[r] ^ k];
cnt[p[r]]++;
}
while (l < q.l) {
cnt[p[l]]--;
ans -= cnt[p[l] ^ k];
l++;
}
while (r > q.r) {
cnt[p[r]]--;
ans -= cnt[p[r] ^ k];
r--;
}
res[q.idx] = ans;
}
uint64_t rhsh = 0;
for (int i = 0; i < m; i++) {
rhsh *= (uint64_t)1e9 + 7;
rhsh += (uint64_t)res[i];
}
cout << rhsh << "\n";
return 0;
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGJpdHNldD4KI2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDxjaHJvbm8+CiNpbmNsdWRlIDxjbGltaXRzPgojaW5jbHVkZSA8Y3N0ZGludD4KI2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxjc3RyaW5nPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPGZzdHJlYW0+CiNpbmNsdWRlIDxmdW5jdGlvbmFsPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxpb21hbmlwPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8bnVtZXJpYz4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8c2V0PgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxzc3RyZWFtPgojaW5jbHVkZSA8dHVwbGU+CiNpbmNsdWRlIDx2ZWN0b3I+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp1c2luZyBuYW1lc3BhY2UgY2hyb25vOwoKI2lmZGVmIERFQlVHCgkvLyNkZWZpbmUgTE9DQUxfSU5QVVRfRklMRQojZWxzZQoJLy8jZGVmaW5lIFVTRV9GSUxFX0lPCiNlbmRpZgoKI2lmZGVmIFVTRV9GSUxFX0lPCgkjZGVmaW5lIElOUFVUX0ZJTEUgImlucHV0LnR4dCIKCSNkZWZpbmUgT1VUUFVUX0ZJTEUgIm91dHB1dC50eHQiCgkjZGVmaW5lIGNpbiBfX19fY2luCgkjZGVmaW5lIGNvdXQgX19fX2NvdXQKCWlmc3RyZWFtIGNpbihJTlBVVF9GSUxFKTsKCW9mc3RyZWFtIGNvdXQoT1VUUFVUX0ZJTEUpOwojZWxzZQoJI2lmZGVmIExPQ0FMX0lOUFVUX0ZJTEUKCQkjZGVmaW5lIGNpbiBfX19fY2luCgkJaWZzdHJlYW0gY2luKCJpbnB1dC50eHQiKTsKCSNlbmRpZgojZW5kaWYKCmNvbnN0IGludCBpbmZpbml0eSA9IChpbnQpMWU5ICsgNDI7CmNvbnN0IGludDY0X3QgbGxJbmZpbml0eSA9IChpbnQ2NF90KTFlMTggKyAyNTY7CmNvbnN0IGludCBtb2R1bGUgPSAoaW50KTFlOSArIDc7IApjb25zdCBsb25nIGRvdWJsZSBlcHMgPSAxZS04OwoKbXQxOTkzN182NCByYW5kR2VuKHN5c3RlbV9jbG9jaygpLm5vdygpLnRpbWVfc2luY2VfZXBvY2goKS5jb3VudCgpKTsKCmlubGluZSB2b2lkIHJhaXNlRXJyb3Ioc3RyaW5nIGVycm9yQ29kZSkgewoJY2VyciA8PCAiRXJyb3IgOiAiIDw8IGVycm9yQ29kZSA8PCBlbmRsOwoJZXhpdCg0Mik7Cn0KCmlubGluZSBpbnQ2NF90IGdpbGJlcnRPcmRlcihpbnQgeCwgaW50IHksIGludCBwb3csIGludCByb3RhdGUpIHsKCWlmIChwb3cgPT0gMCkgewoJCXJldHVybiAwOwoJfQoJaW50IGhwb3cgPSAxIDw8IChwb3ctMSk7CglpbnQgc2VnID0gKHggPCBocG93KSA/ICgKCQkoeSA8IGhwb3cpID8gMCA6IDMKCSkgOiAoCgkJKHkgPCBocG93KSA/IDEgOiAyCgkpOwoJc2VnID0gKHNlZyArIHJvdGF0ZSkgJiAzOwoJY29uc3QgaW50IHJvdGF0ZURlbHRhWzRdID0gezMsIDAsIDAsIDF9OwoJaW50IG54ID0geCAmICh4IF4gaHBvdyksIG55ID0geSAmICh5IF4gaHBvdyk7CglpbnQgbnJvdCA9IChyb3RhdGUgKyByb3RhdGVEZWx0YVtzZWddKSAmIDM7CglpbnQ2NF90IHN1YlNxdWFyZVNpemUgPSBpbnQ2NF90KDEpIDw8ICgyKnBvdyAtIDIpOwoJaW50NjRfdCBhbnMgPSBzZWcgKiBzdWJTcXVhcmVTaXplOwoJaW50NjRfdCBhZGQgPSBnaWxiZXJ0T3JkZXIobngsIG55LCBwb3ctMSwgbnJvdCk7CglhbnMgKz0gKHNlZyA9PSAxIHx8IHNlZyA9PSAyKSA/IGFkZCA6IChzdWJTcXVhcmVTaXplIC0gYWRkIC0gMSk7CglyZXR1cm4gYW5zOwp9CgpzdHJ1Y3QgUXVlcnkgewoJaW50IGwsIHIsIGlkeDsKCWludDY0X3Qgb3JkOwoJCglpbmxpbmUgdm9pZCBjYWxjT3JkZXIoKSB7CgkJb3JkID0gZ2lsYmVydE9yZGVyKGwsIHIsIDIxLCAwKTsKCX0KfTsKCmlubGluZSBib29sIG9wZXJhdG9yPChjb25zdCBRdWVyeSAmYSwgY29uc3QgUXVlcnkgJmIpIHsKCXJldHVybiBhLm9yZCA8IGIub3JkOwp9CgpzaWduZWQgbWFpbigpIHsKCSNpZm5kZWYgVVNFX0ZJTEVfSU8KCQlpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCSNlbmRpZgoJCgltdDE5OTM3IHJuZCg0Mik7CgkKCWludCBuLCBtLCBrOyBjaW4gPj4gbiA+PiBtOyBrID0gcm5kKCkgJSAxMDQ4NTc2OwoJdmVjdG9yPGludD4gcChuKzEpOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspIHsKCQlpbnQgdmFsID0gcm5kKCkgJSAxMDQ4NTc2OwoJCXBbaSsxXSA9IHBbaV0gXiB2YWw7Cgl9CgkKCXZlY3RvcjxRdWVyeT4gcXJ5KG0pOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspIHsKCQlpbnQgbCA9IHJuZCgpICUgbiArIDEsIHIgPSBybmQoKSAlIG4gKyAxOwoJCWlmIChsID4gcikgewoJCQlzd2FwKGwsIHIpOwoJCX0KCQlxcnlbaV0ubCA9IGw7IHFyeVtpXS5yID0gcjsKCQlxcnlbaV0uaWR4ID0gaTsKCQlxcnlbaV0uY2FsY09yZGVyKCk7Cgl9CgkKCWludDY0X3QgYW5zID0gMDsKCXZlY3RvcjxpbnQ2NF90PiByZXMobSk7Cgl2ZWN0b3I8aW50NjRfdD4gY250KChpbnQpMmU2LCAwKTsKCXNvcnQocXJ5LmJlZ2luKCksIHFyeS5lbmQoKSk7CglpbnQgbCA9IDAsIHIgPSAxOwoJYW5zID0gKHBbMV0gPT0gayk7CgljbnRbcFswXV0rKzsgY250W3BbMV1dKys7CgkKCWZvciAoUXVlcnkgcTogcXJ5KSB7CgkJd2hpbGUgKGwgPiBxLmwpIHsKCQkJbC0tOwoJCQlhbnMgKz0gY250W3BbbF0gXiBrXTsKCQkJY250W3BbbF1dKys7CgkJfQoJCXdoaWxlIChyIDwgcS5yKSB7CgkJCXIrKzsKCQkJYW5zICs9IGNudFtwW3JdIF4ga107CgkJCWNudFtwW3JdXSsrOwoJCX0KCQl3aGlsZSAobCA8IHEubCkgewoJCQljbnRbcFtsXV0tLTsKCQkJYW5zIC09IGNudFtwW2xdIF4ga107CgkJCWwrKzsKCQl9CgkJd2hpbGUgKHIgPiBxLnIpIHsKCQkJY250W3Bbcl1dLS07CgkJCWFucyAtPSBjbnRbcFtyXSBeIGtdOwoJCQlyLS07CgkJfQoJCXJlc1txLmlkeF0gPSBhbnM7Cgl9CgkKCXVpbnQ2NF90IHJoc2ggPSAwOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspIHsKCQlyaHNoICo9ICh1aW50NjRfdCkxZTkgKyA3OwoJCXJoc2ggKz0gKHVpbnQ2NF90KXJlc1tpXTsKCX0KCWNvdXQgPDwgcmhzaCA8PCAiXG4iOwoJCglyZXR1cm4gMDsKfQoK