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} $  $ x_{i+1} $ 's is a multiple of $ 3 $ and  for all $ 1<=i<=k $ . The symbol  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