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.IOException;
import java.io.InputStream;
import java.util.StringTokenizer;


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
 
public class Main {
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        public String next() {
            while(tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
    }
    static int maxn = (int)(1e2 + 5);
    static long mod = (long)(1e9 + 7);
    static class Matrix {
    	int n;
    	long[][] a;
    	Matrix(int _n) {
    		n = _n;
    		a = new long[n][n];
    	}
    	Matrix(Matrix m) {
    		n = m.n;
    		a = new long[n][n];
    		for(int i = 0; i < n; ++i) {
    			for(int j = 0; j < n; ++j) {
    				a[i][j] = m.a[i][j];
    			}
    		}
    	}
    	Matrix mul(Matrix m) {
    		Matrix ret = new Matrix(n);
    		for(int i = 0; i < n; ++i) {
    			for(int j = 0; j < n; ++j) {
    				long x = 0;
    				for(int k = 0; k < n; ++k) {
    					x = (x + a[i][k]*m.a[k][j]%mod)%mod;
    				}
    				ret.a[i][j] = x;
    			}
    		}
    		return ret;
    	}
    	Matrix Pow(long k) {
    		Matrix ret = new Matrix(n);
    		for(int i = 0; i < n; ++i) {
    			for(int j = 0; j < n; ++j) {
    				ret.a[i][j] = 0;
    			}
    			ret.a[i][i] = 1;
    		}
    		Matrix bs = new Matrix(this);
    		while(k > 0) {
    			if((k & 1) == 1) {
    				ret = ret.mul(bs);
    			}
    			bs = bs.mul(bs);
    			k >>= 1;
    		}
    		return ret;
    	}
    	void show() {
    		System.out.println("n: " + n);
    		for(int i = 0; i < n; ++i) {
    			for(int j = 0; j < n; ++j) {
    				System.out.print(a[i][j] + " ");
    			}
    			System.out.println();
    		}
    	}
    }
    static long[] b = new long[maxn];
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        long k = in.nextLong();
        for(int i = 0; i < n; ++i) {
        	b[i] = in.nextLong();
        }
        Matrix m = new Matrix(n);
        for(int i = 0; i < n; ++i) {
        	for(int j = 0; j < n; ++j) {
        		long x = (b[i] ^ b[j]);
        		int cnt = 0;
        		while(x > 0) {
        			if((x & 1) == 1) ++cnt;
        			x >>= 1;
        		}
        		if(cnt%3 == 0) m.a[i][j] = 1;
        		else m.a[i][j] = 0;
        	}
        }
//        m.show();
        m = m.Pow(k - 1);
//        m.show();
        long ans = 0;
        for(int i = 0; i < n; ++i) {
        	for(int j = 0; j < n; ++j) {
        		ans = (ans + m.a[i][j])%mod;
        	}
        }
        out.println(ans);
        out.flush();
        out.close();
//   	 	Scanner in = new Scanner(System.in);
//    	in.close();
    }
}

/*


*/