题目背景

天空很蓝。

我抬头看向它。

云朵飘过。

题目描述

在通往世界的尽头，有一条路。路上有 $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$ 个整数表示答案。

5 4
5 4 3 2 1

3

3 10
3 15 31

2

10 16
18 7 9 6 6 2 4 8 5 10

8

提示

今天它飘得很快，目标指向远方。

追逐着云朵的目光望向前方，樱花花瓣飞进我的视线。

对所有数据，满足 $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$	无
#3	$10^5$	B	$\text{30pts}$
#4	$10^6$	无	$\text{50pts}$

特殊性质 A：$A_i$ 相同。

特殊性质 B：$1 \le A_i,m < 2^{20}$。