Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P163SUMJ - ROUND 3J - XOR

Cho một dãy số gồm n phần tử: a[1], a[2], …, a[n]

Một chuỗi gồm các số nguyên x[1], x[2], …, x[k] được gọi là “chuỗi xor”  nếu với mọi i mà 1 <= i <= k – 1 thì số bit của x[i] xor x[i + 1] sẽ chia hết cho 3 và x[p] thuộc {a[1], a[2], .., a[n]}, với 1 <= p <= k.

Vậy có tất cả bao nhiêu “chuỗi xor”?

Chú ý nếu a = [1, 1] và k = 1 thì kết quả sẽ là 2, vì ta coi mỗi phần tử từ a là phân biệt.

Input

Dòng đầu tiên gồm 2 số nguyên n và k (1 <= n <= 100, 1 <= k <= 10^18) lần lượt là số phần tử của dãy a và độ dài của của “chuỗi xor”.

Dòng thứ 2 gồm n số nguyên là các phần tử của dãy a (1 <= a[i] <= 10^18)

Output

In ra một số nguyên là số lượng “chuỗi xor” sau khi đã lấy dư cho 10^9 + 7.

Example

Input:
4 2
1 1 1 1 Output: 16

Được gửi lên bởi:Admin
Ngày:2016-07-22
Thời gian chạy:1s-2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.