Educational Codeforces Round 14 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

matrices

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Xor-sequences

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Input

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}).

Output

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

Examples

Input

5 2

15 1 2 4 8

Output

13

Input

5 1

15 1 2 4 8

Output

5

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/04/2023 12:47:04 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|