解锁成就：半夜过题。（其实是因为在搞bsd）
仔细看下题推一下发现第n维中m维元素的个数为2^(n-m)*C(n,m)。
然后组合数好像得nlogn用逆元？恭喜tle。
然后yy了一个用线性筛的办法，只是素数用快速幂，这样大约可以降低复杂度，然后就能过了。好神奇。
代码好长TT。
#include <cstdio>
#include <cstring>
#define _l (long long int)
const int maxn = 10000009;
int tp, pn[maxn], inv[maxn];
bool pr[maxn];
int n, mod, s, c, p;
int modPow(int a, int x) {
int s = 1;
for (; x; x >>= 1, a = _l a * a % mod)
if (x & 1)
s = _l s * a % mod;
return s;
}
void pre(int n) {
memset(pr, 0, sizeof(pr));
inv[1] = 1;
tp = 0;
for (int i = 2; i <= n; ++ i) {
if (!pr[i]) {
pn[tp ++] = i;
inv[i] = modPow(i, mod - 2);
}
for (int j = 0; j < tp && i * pn[j] <= n; ++ j) {
pr[i * pn[j]] = 1;
inv[i * pn[j]] = _l inv[i] * inv[pn[j]] % mod;
if (i % pn[j] == 0)
break;
}
}
}
int main() {
scanf("%d%d", &n, &mod);
pre(n);
c = 1;
p = 1;
s = 0;
for (int i = 0; i <= n; ++ i) {
s ^= _l c * p % mod;
p = p * 2 % mod;
c = _l c * inv[i + 1] % mod * (n - i) % mod;
}
printf("%d\n", s);
}
upd: mhy大神出了组数据把我卡掉了。结果是n>mod的时候要考虑mod的倍数的问题。好厉害orz