Phép AND bitwise (ký hiệu là &) so sánh từng bit của 2 số, bit kết quả là 1 nếu cả 2 bit cùng là 1, ngược lại là 0. Cho mảng A gồm N số nguyên dương. Hãy tính tổng của phép toán (Ai & Aj) với mọi cặp chỉ số 1 <= i < j <= N. Kết quả có thể rất lớn, hãy in phần dư khi chia cho 10^9+7.

Input:

Dòng 1: N (2 <= N <= 10^5).

Dòng 2: N số nguyên Ai (0 <= Ai <= 10^9).

Output: Tổng AND của mọi cặp modulo 10^9+7.

Ví dụ:

Input:

3
1 2 3

Output:

3

(Giải thích: (1&2) + (1&3) + (2&3) = 0 + 1 + 2 = 3. Xin lỗi, phép toán 1&2=0, 1&3=1, 2&3=2. Tổng bằng 3).

Hệ thống AI nhận diện được N điểm sáng trên mặt phẳng tọa độ Oxy. Bạn hãy lập trình đếm xem từ N điểm này có thể tạo thành bao nhiêu hình chữ nhật có các cạnh song song với trục tọa độ. (4 điểm tạo thành 1 hình chữ nhật nếu chúng có tọa độ dạng (x1, y1), (x2, y1), (x2, y2), (x1, y2)).

Input:

Dòng 1: Số nguyên N (1 <= N <= 2000).

N dòng tiếp theo: Mỗi dòng 2 số nguyên x, y là tọa độ của một điểm (-10^4 <= x, y <= 10^4). Không có 2 điểm nào trùng nhau.

Output: Số lượng hình chữ nhật thỏa mãn.

Ví dụ:

Input:

6
0 0
0 1
1 0
1 1
0 2
1 2

Output:

3

Bạn là một xạ thủ phòng thủ cứ điểm. Có N quái vật xuất hiện, quái vật thứ i xuất hiện tại thời điểm Ti và sẽ biến mất tại thời điểm Di (bạn chỉ có thể bắn nó trong khoảng từ Ti đến Di). Việc nhắm bắn tiêu diệt đúng 1 quái vật tiêu tốn của bạn đúng 1 đơn vị thời gian. Hãy sắp xếp lịch bắn sao cho tiêu diệt được nhiều quái vật nhất.

Input:

Dòng 1: N (1 <= N <= 10^5).

N dòng tiếp theo: Mỗi dòng 2 số nguyên Ti, Di (1 <= Ti <= Di <= 10^9).

Output: Số lượng quái vật lớn nhất bị tiêu diệt.

Ví dụ:

Input:

4
1 2
1 2
2 3
3 4

Output:

4

(Giải thích: Bắn quái 1 ở t=1, quái 2 ở t=2, quái 3 ở t=3, quái 4 ở t=4).

Cho một chuỗi ký tự chỉ gồm 2 loại dấu ngoặc: '(' và ')'. Bạn hãy tìm độ dài của chuỗi con liên tiếp hợp lệ (các ngoặc đóng mở đúng quy tắc) dài nhất trong chuỗi đã cho.

Input: Một chuỗi ký tự (Độ dài <= 10^5).

Output: Độ dài chuỗi con hợp lệ lớn nhất.

Ví dụ:

Input:

)((()())(

Output:

6

(Giải thích: Chuỗi con hợp lệ dài nhất là "(()())" ở giữa).