题目描述

给定长度为 $n$ 的序列 $a$ ， 你需要计算有多少组不同的 $(i,j,k,l)$ 满足：

1. $i<j<k<l$ 且是 $[1,n]$ 间的整数。

2. $a_i\oplus a_j\oplus a_k\oplus a_l=0$ ，这里 $\oplus$ 是异或运算。

为了降低难度，我们给出 $m$ ，令以上答案是 $A$ ，你只需要输出 $\min (A,m)$ 即可。

保证对于 $i\neq j$ ，$a_i\neq a_j$ 。

输入格式

第一行包含两个整数 $n,m$ ，$n$ 表示序列 $a$ 的长度，$m$ 含义如题目描述所示。

第二行包含 $n$ 个整数，第 $i$ 个整数表示 $a_i$ 。

输出格式

一行一个整数，表示 $\min(A,m)$ 。

样例

样例输入

8 100
1 2 3 4 5 6 7 8

样例输出

7

数据范围

对于所有数据，$1 \le n,m\le 10^5,0\le a_i<2^{18}$ ，对于 $i\neq j,a_i\neq a_j$。

子任务 1 ( 20% ) : $n\le 100$ 。

子任务 2 ( 30% ) : $n\le 500$ 。

子任务 3 ( 20% ) : $n\le 3000$ 。

子任务 4 ( 30% ) : 无特殊限制。