Trong một dự án nghiên cứu tại Trung tâm Công nghệ UMT, bạn được giao nhiệm vụ tối ưu hóa năng lượng trong một hệ thống gồm n thiết bị điện tử. Mỗi thiết bị có một mức năng lượng ban đầu, được biểu diễn bằng một số nguyên không âm. Bạn có thể thực hiện các thao tác sau bất kỳ số lần nào:

• Chọn hai thiết bị khác nhau, ký hiệu là ~i~ và ~j~.

• Cập nhật mức năng lượng của thiết bị ~i~ thành ~a_i ← a_i~ AND ~a_j~ (phép AND bitwise).

• Cập nhật mức năng lượng của thiết bị ~j~ thành ~a_j ← a_i~ OR ~a_j~ (phép OR bitwise).

Sau khi thực hiện các thao tác, bạn cần chọn ra k thiết bị và tính tổng bình phương mức năng lượng của chúng. Mục tiêu là tối đa hóa tổng này. Do kết quả có thể rất lớn, hãy in ra tổng bình phương mức năng lượng lớn nhất có thể đạt được, lấy MOD~10^9+7~.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 ≤ k ≤ n ≤ 10^5)~ — số lượng thiết bị và số thiết bị cần chọn.

Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, . . . , a_n (0 ≤ a_i < 2^30)~ — mức năng lượng ban đầu của các thiết bị.

Output

In ra một số nguyên duy nhất — tổng bình phương mức năng lượng lớn nhất có thể đạt được sau các thao tác, MOD ~10^9 + 7~.

Sample Input 1

3 2
3 8 2

Sample Ouput 1

125

Sample Input 2

3 3
1 3 5

Sample Ouput 2

51

Subtask:

• Subtask 1 (10% số điểm): ứng với ~n ≤ 10^4~

• Subtask 2 (90% số điểm): không giới hạn gì thêm.