Tý có một trường học có \(N\) học sinh, mỗi em có mã số tài năng \(A[i]\) (\(0 \le A[i] < 2^K\)). Hai học sinh được gọi là "hợp cạ" nếu họ không có chung bất kỳ tài năng nào, tức là \(A[i] \& A[j] = 0\).

Hãy đếm số cặp học sinh hợp cạ.

Đầu vào:

• Dòng 1: \(N, K\) (\(N \le 10^5, K \le 20\))
• Dòng 2: \(N\) số nguyên \(A[1..N]\) (\(0 \le A[i] < 2^K\))

Đầu ra:

• Một số nguyên duy nhất là số cặp \((i, j)\) với \(i < j\) thỏa mãn \(A[i] \& A[j] = 0\).

Ví dụ: \(N=4, K=2, A=[0,1,2,3]\) → Các cặp: \((0, 1)\),\((0, 2)\),\((0, 3)\),\((1, 2)\) → 4.

#

Định dạng đầu vào

• Dòng 1: Hai số nguyên \(N\) và K (\(1 \le N \le 10^5, 1 \le K \le 20\)).
• Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(0 \le a_i < 2^K\)).

Định dạng đầu ra

• In ra số lượng tập con thỏa mãn modulo \(10^9+7\).

Ví dụ

Input:

3 3
1 2 3

Output:

4

Giải thích: Các tập con thỏa mãn điều kiện bit.

Ràng buộc & Subtasks