Cho một dãy số nguyên dương \(a = a_{1}, a_{2}, \ldots, a_{n}\) và một số \(k\). Một tập con \(S\) của \(\{1, 2, \ldots, n\}\) được gọi là tập xor nếu \(S\) có không quá \(k\) phần tử và với mọi \(i, j\) thuộc \(S\) ta có \(a_{i} + a_{j} = a_{i} \oplus a_{j}\). Ở đây \(\oplus\) là phép toán xor (tổng nim, cộng không nhớ hay hoặc triệt tiêu). Trọng số của \(S\) được hiểu là tổng tất cả các \(a_{i}\), với \(i\) thuộc \(S\).

Yêu cầu: Hãy tính tổng trọng số tất cả các tập xor.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \leq n \leq 10^{1000})\).
• Dòng thứ hai chứa số nguyên dương \(k\) \((1 \leq k \leq 10^{1000})\).
• Nếu \(n \leq 10^{4}\) thì dòng thứ ba chứa \(n\) số, số thứ \(i\) là \(a_{i}\) . Nếu \(n > 10^{4}\) thì không có dòng thứ ba.

Output

• Ghi ra tổng trọng số tất cả các tập xor, sau khi chia lấy dư cho \(10^{9} + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \leq n, k, a_{i} \leq 10^{2}\).
• Subtask \(2\) (\(20\%\) số điểm): \(1 \leq n, k, a_{i} \leq 10^{3}\).
• Subtask \(3\) (\(20\%\) số điểm): \(1 \leq n, k \leq 10^{4}\) và \(a_{i} = i\).
• Subtask \(4\) (\(20\%\) số điểm): \(1 \leq n, k, a_{i} \leq 10^{4}\).
• Subtask \(5\) (\(20\%\) số điểm): \(a_{i} = i\).

Example

6
3
1 1 2 3 4 5

66