Problem: 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 <image> xi + 1's is a multiple of 3 and <image> for all 1 ≤ i ≤ k. The symbol <image> 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

Solution (in JAVA):

Solution:
import java.io.* ;
import java.math.* ;
import java.text.DecimalFormat;
import java.util.* ;
public class Codeshefcode {
	final static long r = 1000000007 ;
	static FasterScanner ip = new FasterScanner() ;
	static PrintWriter op = new PrintWriter(System.out) ; 
	public static void main(String[] args) throws IOException{
	    int n = ip.i() ;
	    long k = ip.l() ;
	    long a[] = new long[n] ;
	    for(int i=0 ; i<n ; i++)
	    	a[i]=ip.l() ;
		long vec[] = new long[n] ;
		for(int i=0 ; i<n ; i++)
			vec[i]=1 ;
		long A[][] = new long[n][n] ;
		for(int i=0 ; i<n ; i++)
			for(int j=0 ; j<n ; j++)
				A[i][j]=Long.bitCount(a[i]^a[j])%3==0 ? 1 : 0 ;
		MatrixOperations Mop = new MatrixOperations(n) ;
		vec = Mop.m(vec,Mop.Pow(A,k-1)) ;
		long ans=0 ;
		for(int i=0 ; i<n ; i++)
			ans = (ans+vec[i])%r ;
		op.print(ans) ;
		Finish() ;
	}	
	static void Finish(){
		op.flush(); 
		op.close();
	}
}
class MatrixOperations{
	final static long r = 1000000007 ;
	long[][] I ;
	int N ;
	MatrixOperations(int size){
		N=size ;
		I = new long[N][N] ;
		for(int i=0 ; i<N ; i++)
			for(int j=0 ; j<N ; j++)
				I[i][j]=(i==j) ? 1 : 0 ;
	}
	long[][] m(long[][] A1,long[][] A2){
		long A[][] = new long[N][N] ;
		for(int i=0 ; i<N ; i++)
			for(int j=0 ; j<N ; j++){
				long t=0 ;
				for(int k=0 ; k<N ; k++)
					t = (t+(A1[i][k]*A2[k][j])%r)%r ;
				A[i][j]=t ;
			}	
		return A ;
	}
	long[][] Pow(long[][] A,long pow){
		if(pow==0)
			return I ;
		if(pow==1)
			return A ;
		long[][] hp = Pow(A,pow/2) ;
		long[][] fp = m(hp,hp) ;
		if(pow%2==0)
			return fp ;
		else
			return m(A,fp) ;
	}
	long[] m(long[] vec,long[][] mat){
		long ans[] = new long[N] ;
		for(int i=0 ; i<N ; i++){
			long t=0 ;
			for(int k=0 ; k<N ; k++)
				t=(t+(vec[k]*mat[k][i])%r)%r ;
			ans[i]=t ;
		}
		return ans ;
	}
}
@SuppressWarnings("serial") 
class MyList extends ArrayList<Integer>{
	
}

class pair implements Comparable<pair>{
	private long x ;
	private int y ;
	pair(long a,int b){
		x=a ;
		y=b ;		
	}
	public long x(){
		return x ;
	}
	public int y(){
		return y ;
	}
	public int compareTo(pair p){
		int l = Long.compare(this.x,p.x) ;
		if(l!=0)
			return l ;
		return Integer.compare(this.y,p.y) ;
	}
}
class FasterScanner {
 
    private InputStream mIs;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
 
    public FasterScanner() {
        this(System.in);
    }
 
    public FasterScanner(InputStream is) {
        mIs = is;
    }
 
    public int read() {
        if (numChars == -1) {
            throw new InputMismatchException();
    
    }
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = mIs.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0) {
                return -1;
            }
        }
        return buf[curChar++];
    }
 
    public String nextLine() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isEndOfLine(c));
        return res.toString();
    }
 
    public String S() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }
 
    public long l() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
 
    public int i() {
        int c = read();
        while (isSpaceChar(c)) {
            c = read();
        }
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
 
    public boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
 
    public boolean isEndOfLine(int c) {
        return c == '\n' || c == '\r' || c == -1;
    } 
}