Xor-sequences

题意翻译

Problem Description 给定一个数集A,现在你需要构造一个长度为k的序列B,序列B的元素从数集A中任意挑选,要求B中任意相邻的两个数字的异或值二进制表示中1的个数是3的倍数,请问B的有多少种合法的构造方案?两种方案不同当且仅当存在Bi在A中的位置不同。 Input 第一行两个数字n和k,表示数集大小和序列B的长度, 接下来一行有n个数字,代表数集中的元素。 40%的数据:1≤n≤100,1≤k≤10000,0≤ai≤10^18 100%的数据:1≤n≤100,1≤k≤10^18,0≤ai≤10^18 Output 输出一行,表示答案,由于答案可能会很大,请对10^9+7取模后输出。

题目描述

You are given $ n $ integers $ a_{1},a_{2},...,a_{n} $ . A sequence of integers $ x_{1},x_{2},...,x_{k} $ is called a "xor-sequence" if for every $ 1<=i<=k-1 $ the number of ones in the binary representation of the number $ x_{i} $ ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF691E/081f686069870b762728923799c454e27369af9a.png) $ x_{i+1} $ 's is a multiple of $ 3 $ and ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF691E/187abd20483c4318d7cd71518f323b9990bcdd61.png) for all $ 1<=i<=k $ . The symbol ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF691E/081f686069870b762728923799c454e27369af9a.png) is used for the binary exclusive or operation. How many "xor-sequences" of length $ k $ exist? Output the answer modulo $ 10^{9}+7 $ . Note if $ a=[1,1] $ and $ k=1 $ then the answer is $ 2 $ , because you should consider the ones from $ a $ as different.

输入输出格式

输入格式


The first line contains two integers $ n $ and $ k $ ( $ 1<=n<=100 $ , $ 1<=k<=10^{18} $ ) — the number of given integers and the length of the "xor-sequences". The second line contains $ n $ integers $ a_{i} $ ( $ 0<=a_{i}<=10^{18} $ ).

输出格式


Print the only integer $ c $ — the number of "xor-sequences" of length $ k $ modulo $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

5 2
15 1 2 4 8

输出样例 #1

13

输入样例 #2

5 1
15 1 2 4 8

输出样例 #2

5