峡国西高校 (hard version)

题号：NC282535
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

本题 easy version 的唯一区别是，本题需要求解一个序列中任两个不同的数的 $k$ 进制异或和的和。

题目背景

「这样一来，你还没有意识到吗？自己的错误在哪里？」
「——什么！」
即便如此，我——
我也要先否定现实（你）。
「你，你……为什么要设计如此精细的行动……」
「我的目的一直都没有改变过。」
我点击了一下手机屏幕，轻轻地揣入胸前的口袋中。一下子挺直腰杆，与清里同学正面相对。
接着，深深地吸了一口气。
终于，对着“女主角”宣扬出了自己真意。
「我想要做什么，这个始终都是一致的！只有一件事。
在这只有一次的高中生涯中，实现最好的“理想乡（爱情喜剧）”，达成“完美无缺的happy end”——仅此而已！」

题目描述

有 $n$ 个点，我们认为第 $i$ 个点的特征值为 $a_i$ 。
我们认为两个点组在一起的权重为 $k$ 进制下特征值的异或和（也就是 $k$ 进制下的不进位加法），而这个序列的权重为任选两个不同的点，将他们组合的权重之和。
现在你需要求出这个序列的权重，对 $10^9+7$ 取模。

数据范围

$1\leqslant n\leqslant 2\times10^6,2\leqslant k\leqslant 500,1\leqslant a_i\leqslant 10^{18}$ 。

输入描述:

第一行两个正整数 ，分别表示序列长度与进制。
第二行  个正整数，第  个正整数为  表示第  个数的特征值。

输出描述:

一行，一个正整数，表示这个序列的权重，对  取模。

示例1

输入

复制

2 5
4 8

输出

复制

示例2

输入

复制

8 16
32178 3216 31268 31280 3879 34278 3728 217

输出

复制