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~.

Yêu cầu: Tính tổng các ~f(l, r)~ và lấy phần dư khi chia cho ~10^9 + 7~.

Input

• 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 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~.

Sample Input 1

3
1 2 3

Sample Output 1

8