Cho dãy \(a\) gồm \(n\) phần tử, được đánh số từ \(1\) tới \(n\). Ta gọi \(f(l, r)\) là số lớn nhất có dạng \(2^x\) sao cho tổng của các số \(a_l, a_{l+1}, \dots, a_r\) chia hết cho \(2^x\). Nhiệm vụ của bạn là tính tổng của tất cả các \(f(l, r)\) với \(1 \le l \le r \le n\).

Input

• Dữ liệu vào từ file văn bản VARR.INP:
  • Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 2 \times 10^5\)) tương ứng là độ dài của dãy \(a\).
  • Dòng thứ hai chứa \(n\) số nguyên mô tả dãy \(a\), số nguyên thứ \(i\) là giá trị của \(a_i\) (\(1 \le a_i \le 10^6\), \(\sum_{i=1}^{n} a_i \le 10^6\)).

Output

• Ghi ra file văn bản VARR.OUT:
  • Ghi kết quả trên một dòng, là kết quả của bài toán sau khi lấy phần dư khi chia cho \(10^9 + 7\).

Example

3
1 2 3

8

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 200\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 5000\).
• Subtask \(3\) (\(25\%\) số điểm): \(\sum_{i=1}^{n} a_i \le 2 \times 10^5\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.