Khoảnh khắc Lapras đóng băng thành công tấc dung nham cuối cùng của Groudon, Ash chưa kịp thở phào nhẹ nhõm thì cảnh vật không gian xung quanh bỗng chốc méo mó, rạn nứt như những mảnh thủy tinh vỡ vụn. Lực hấp dẫn hoàn toàn đảo lộn, vạn vật mất trọng lượng, và cậu nhận ra mình đã bị hút sâu vào một thực tại hoàn toàn khác: Chiều Không Gian Ảo Ảnh - tàn dư vĩ đại và cũng là cạm bẫy cuối cùng, đáng sợ nhất của Team Rocket. Kẻ đứng sau giật dây mọi chuyện, thao túng vạn vật nãy giờ từ từ hạ cánh xuống từ bầu trời hắc ám. Không ai khác, đó chính là thực thể đột biến Mewtwo, nhưng giờ đây nó đang ở trong một trạng thái tồi tệ tột độ: toàn bộ cơ thể bị kìm kẹp bởi một bộ giáp hắc ám công nghệ cao do Giovanni chế tạo nhằm kiểm soát trí não của nó. Ánh mắt Mewtwo đỏ ngầu sự thịnh nộ và mất kiểm soát. Để ngăn cản bước tiến của Ash, Mewtwo sử dụng siêu năng lực khuếch đại vô cực của mình, ngay lập tức phân rã các hạt ánh sáng và tạo ra \(N\) ảo ảnh phân thân bay lơ lửng, thoắt ẩn thoắt hiện khắp mọi ngóc ngách của không gian đa chiều này. Theo phân tích thần tốc từ hệ thống siêu máy tính vệ tinh của Professor Oak truyền xuống Pokedex, mỗi một ảo ảnh không chỉ là một cái bóng vô tri, mà chúng mang theo một đoạn mã gen di truyền nhân tạo được biểu diễn dưới dạng một số nguyên không âm cực kỳ phức tạp. Dãy mã gen của \(N\) phân thân này được hệ thống đánh số thứ tự từ \(1\) đến \(N\) lần lượt mang các giá trị là \(A_1, A_2, \dots, A_N\).

Nhiệm vụ cứu rỗi thế giới đặt trọn lên vai Ash: để phá vỡ kết giới hắc ám dày đặc này và giải cứu linh hồn Mewtwo khỏi sự kiểm soát bạo chúa của bộ giáp, Ash phải ra lệnh cho 3 Pokemon chủ lực của mình đứng thành đội hình tam giác, đồng loạt tụ khí để tung ra đòn tấn công hợp thể huyền thoại mang tên "Tri-Attack". Điều kiện tiên quyết là cậu cần phải khóa máy nhắm chuẩn xác vào đúng 3 phân thân mục tiêu trên bầu trời (do tính chất lượng tử của ảo ảnh, cậu hoàn toàn có thể chọn lặp lại cùng một vị trí phân thân nhiều lần cho các tia đánh khác nhau, tức là phải chọn ra một bộ ba chỉ số ngắm bắn \((i, j, k)\) với điều kiện \(1 \le i, j, k \le N\)). Sự kết hợp năng lượng tinh khiết của 3 phân thân bị đánh trúng sẽ sinh ra một vụ nổ cộng hưởng hạ nguyên tử, làm triệt tiêu hoàn toàn và vĩnh viễn năng lượng hắc ám của không gian chiều sâu này nếu và chỉ nếu mã gen của ba phân thân đó giao thoa và triệt tiêu lẫn nhau về mức 0 tuyệt đối. Ngôn ngữ của máy tính diễn giải điều này như sau:

(Trong đó, AND là phép toán thao tác bit chuẩn - Bitwise AND, so sánh từng bit nhị phân một của ba con số). Trận chiến sinh tử này chỉ còn được tính bằng từng tích tắc nhỏ nhoi, vạn vật sắp sụp đổ. Bạn hãy dốc toàn bộ vốn liếng của một cao thủ lập trình thi đấu để giúp Ash tính toán khẩn cấp xem tổng cộng hệ thống radar có bao nhiêu bộ ba chỉ số ngắm bắn \((i, j, k)\) thỏa mãn điều kiện triệt tiêu tuyệt đối này.

Lưu ý quan trọng: Cấu trúc tọa độ ngắm \((1, 2, 3)\) và \((2, 1, 3)\) được coi là hai phương án khóa mục tiêu hoàn toàn khác nhau biệt lập, bởi vì thứ tự phân công mục tiêu cho 3 Pokemon của Ash là khác nhau.

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^6\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(0 \le A_i < 2^{20}\)).

Output

• In ra một số nguyên duy nhất là tổng số lượng bộ ba chỉ số \((i, j, k)\) hợp lệ để kích hoạt thành công Đòn Đánh Ba Tia.

Example

3
1 2 4

24

4
3 5 6 7

6

5
0 0 0 0 0

125

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(N \le 100\), \(A_i < 2^{10}\).
• Subtask \(2\) (\(30\%\) điểm): \(N \le 5000\), \(A_i < 2^{12}\).
• Subtask \(3\) (\(50\%\) điểm): Không còn ràng buộc gì thêm.