4660: Xor-sequences
内存限制：256 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：6
通过：3
题目描述
E. Xor-sequences
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
有n个整数a1,a2,...,an.
整数序列x1,x2,...,xk，如果对于每1≤i≤k-1，数字xi 
xi+1的二进制表示中的1个数是3的倍数，并且对于所有1≤i≤k,xi 属于{a1,a2,...,an}，这称为“xor序列”。符号用于二进制异或运算。
请问有多少种合法的构造序列
Input
第一行两个数字n和k，表示数集大小和所需构造序列的长度， 接下来一行有n个数字，代表数集中的元素。
Output
输出一行，表示答案，由于答案可能会很大，请对10^9+7取模后输出。
You are given n integers a1,a2,...,an.
A sequence of integers x1,x2,...,xk is called a "xor-sequence" if for every 1≤i≤k-1 the number of ones in the binary representation of the number xi
xi+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 109+7.
Note if a=[1,1] and k=1 then the answer is 2, because you should consider the ones from a as different.
A sequence of integers x1,x2,...,xk is called a "xor-sequence" if for every 1≤i≤k-1 the number of ones in the binary representation of the number xi
xi+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 109+7.
Note if a=[1,1] and k=1 then the answer is 2, because you should consider the ones from a as different.
Input
The first line contains two integers n and k (1≤n≤100, 1≤k≤1018) − the number of given integers and the length of the "xor-sequences". The second line contains n integers ai (0≤ai≤1018).
Output
Print the only integer c − the number of "xor-sequences" of length k modulo 109+7.
Examples
Input
5 2 15 1 2 4 8
Output
13
Input
5 1 15 1 2 4 8
Output
5
输入格式
输出格式
输入样例 复制
输出样例 复制