Tại Viện Nghiên cứu Trí tuệ Nhân tạo UMT, các sinh viên được giao một đề tài đặc biệt: mô phỏng quá trình hình thành kim tự tháp XOR — một cấu trúc dữ liệu bí ẩn lấy cảm hứng từ cổ ngữ Ai Cập và toán học hiện đại. Kim tự tháp XOR được xây dựng như sau:

• Dòng dưới cùng (đáy) gồm ~n~ số nguyên.

• Mỗi số nằm ở tầng phía trên là phép XOR giữa hai số ngay phía dưới bên trái và bên phải của nó.

• Quá trình tiếp tục cho đến khi đạt đến đỉnh kim tự tháp, tức là chỉ còn một số duy nhất.

Ví dụ:

Tuy nhiên, hệ thống lượng tử ở UMT lại không ổn định, nên mỗi lần khởi tạo kim tự tháp, dãy đáy lại bị xáo trộn một cách ngẫu nhiên. Nhiệm vụ của bạn là tính giá trị kỳ vọng của số nằm ở đỉnh kim tự tháp, xét trên tất cả các hoán vị có thể của dãy đáy. Do giá trị kỳ vọng có thể là phân số ~p/q~, bạn cần in ra một số nguyên ~x~ sao cho:

~p.q≡p (MOD10^9 + 7)~

Input

Dòng đầu tiên là một số nguyên ~n~ ~(1 ≤ n ≤ 2^9)~ — số phần tử của đáy kim tự tháp.

Dòng thứ hai gồm ~n~ số nguyên phân biệt ~a_1, a_2 . . . , a_n (0 ≤ ai < 2^9)~ — dãy đáy ban đầu.

Output

In ra một số nguyên duy nhất x là kết quả theo mô tả ở trên.

Sample Input 1

2
1 3

Sample Ouput 1

2

Sample Input 2

5
2 3 1 2 3

Sample Ouput 2

800000007

Giải thích

Với trường hợp đầu tiên, có 2 hoán vị: [1, 3] và [3, 1]. Đỉnh của [1, 3] là 1 ⊕ 3 = 2, còn đỉnh của [3, 1] cũng là 3 ⊕ 1 = 2. Do đó kỳ vọng là 2.

Subtask:

• Subtask 1 (10% số điểm): ~n ≤ 10~.

• Subtask 2 (20% số điểm): ~n ≤ 20~.

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