Chụp hình bạn bè

Bạn có \(n\) người bạn và muốn chụp \(m\) tấm hình cho họ. Mỗi tấm hình phải chụp đúng hai người bạn, và không có cặp bạn nào được chụp hơn một lần. Nói cách khác, mỗi tấm hình là một cặp \((i, j)\) với \(1 \le i < j \le n\) và mỗi cặp chỉ được chọn một lần.

Mỗi người bạn thứ \(i\) có một mức độ thu hút được biểu diễn bởi số nguyên \(a_i\). Độ hấp dẫn của một bức hình chụp hai người bạn \(i\) và \(j\) được tính bằng \(a_i \oplus a_j\), trong đó \(\oplus\) là phép toán XOR giữa hai số nguyên.

Hãy chọn ra \(m\) tấm hình sao cho tổng độ hấp dẫn là lớn nhất có thể. Do kết quả có thể rất lớn, hãy in ra phần dư của tổng độ hấp dẫn chia cho \(10^9 + 7\).

Input

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((2 \le n \le 10^5,\ 1 \le m \le \frac{n(n-1)}{2})\) --- số người bạn và số tấm hình cần chụp.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((0 \le a_i \le 10^9)\) --- mức độ thu hút của từng người bạn.

Output

• Ghi ra một số nguyên duy nhất --- tổng độ hấp dẫn lớn nhất có thể đạt được sau khi chụp \(m\) tấm hình, lấy modulo \(10^9 + 7\).

Example

3 2
1 2 3

5

3 3
1 2 3

6

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 15 & \(n \le 1000\)

2 & 20 & \(a_i \lt 2^{10}\) với mọi \(i\)

3 & 65 & Không có ràng buộc bổ sung

\hline
\endtabular