P14200 朝向过去的远方

天空很蓝。 我抬头看向它。 云朵飘过。

在通往世界的尽头，有一条路。路上有 $n$ 个点，其中从前往后第 $i$ 个点的记忆度为 $A_i$。 抱月朝前走着。因为不想忘记太多，到点 $i$ 时，她会询问对于从 $i$ 到 $n$ 的每个点 $x$，最小的 $j$ 的值，满足 $A_j,A_{j+1},\dots,A_x$ 按位与的结果和 $A_{i},A_{i+1},\dots,A_{x}$ 按位与的结果相同。 也许是记忆力不太好，对于每个 $i$，记 $s(i)$ 为 $x=i,i+1,\dots,n$ 时对应的 $j$ 与 $i$ 的距离（$|i-j+1|$）的按位异或和。请你在她走到尽头时，告诉她 $\sum\limits_{i=1}^{n}s(i) \bmod m$ 的值。 **【形式化题面】**: 给定一个长度为 $n$ 的序列 $A$。 记 $g(l,r)=(A_l\&A_{l+1}\&\dots\& A_r)$，$f(r,x)=\min\limits_{1 \le l \le r \land g(l,r)=x }^{}l$。 输出 $\sum\limits_{i=1}^{n} (\bigoplus\limits_{r=i}^{n}(i-f(r,g(i,r))+1)) \bmod m$ 的值。

第一行两个整数 $n,m$。 第二行 $n$ 个整数 $A_i$。

一行 $1$ 个整数表示答案。

今天它飘得很快，目标指向远方。 追逐着云朵的目光望向前方，樱花花瓣飞进我的视线。 对所有数据，满足 $1 \le n \le 10^6,1 \le A_i,m < 2^{30}$。 ::cute-table{tuack} |子任务编号|$n\le$|特殊性质|分值| |:-:|:-:|:-:|:-:| |#1|$10^6$|A|$\text{10pts}$| |#2|$10^3$|无|$\text{10pts}$| |#3|$10^5$|B|$\text{30pts}$| |#4|$10^6$|无|$\text{50pts}$| 特殊性质 A：$A_i$ 相同。 特殊性质 B：$1 \le A_i,m < 2^{20}$。