当前没有测试数据。

5.运动积分

题目描述

一年一度的运动会开始了。

有$N$个选手参赛，第$i$个选手有一个能力值$A_i$（保证$A_i$两两不同），比赛一共进行了$2^M$天。

在第$j$天（$0 \leq j \leq 2^M-1$）的比赛中，第$i$个选手的得分为$A_i \oplus j$，然后从大到小排名，排名为$x$（$x$从$0$开始）的同学会获得$x^2$的积分，你需要求出每个同学最后总的积分和$q_i \bmod (10^9+7)$的结果$p_i$。

为了避免输出文件过大，你只要输出$p_i$的异或和即可。

输入格式

第一行两个整数，分别代表$N$，$M$。

接下来一行$N$个整数，第$i$个数代表$A_i$。

输出格式

一个整数代表答案。

数据范围与提示

• 对于$10\%$的数据，$1 \leq M \leq 5$；
• 对于$30\%$的数据，$1 \leq N \leq 100$；
• 对于$50\%$的数据，$1 \leq N \leq 1000$；
• 对于$100\%$的数据，$1 \leq N \leq 200000$，$0 \leq M \leq 30$，$A_|i| < 2^M$。

样例

3 2
0 1 2

8