Giao Bằng Không · canuc80k4610 · Thuật toán Canuc80k

Cho một dãy số nguyên không âm. Hãy đếm số cách chọn một tập con không rỗng của các vị trí sao cho phép AND bit của toàn bộ giá trị được chọn bằng $0$ . Hai tập con khác nhau nếu chúng khác ít nhất một vị trí, kể cả khi các giá trị tại những vị trí đó bằng nhau.

Input

Dòng đầu chứa số nguyên $n$ . Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Output

In số tập con thỏa mãn, lấy modulo $1000000007$ .

Constraints

$1 \leq n \leq 1 0^{6}$ .
$0 \leq a_{i} \leq 1 0^{6}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 22$ và $a_{i} < 2^{10}$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

3
1 2 3

Output

Giải thích: Có đúng hai tập con cho AND bằng $0$ : chọn hai vị trí mang $1, 2$ , hoặc chọn cả ba vị trí. Các tập con còn lại có AND khác $0$ .

Phân tích: Một tập con có AND bằng 0 khi không tồn tại bit nào xuất hiện trong tất cả phần tử được chọn. Dùng bao hàm-loại trừ trên các bit chung. Với mask m, số vị trí chứa toàn bộ bit của m được lấy bằng superset zeta.
Thuật toán: Đếm tần suất trên 2^20 mask và chạy superset zeta, thu superCnt[m]. Có 2^{superCnt[m]}-1 tập con không rỗng mà mọi phần tử đều chứa m. Cộng đại lượng này với dấu (-1)^{popcount(m)} trên mọi m.
Chứng minh đúng đắn: Với mỗi bit b, gọi E_b là sự kiện bit đó còn trong AND của tập đã chọn. Đáp án là số tập không thuộc hợp các E_b. Giao các sự kiện ứng với mask m yêu cầu mọi phần tử được chọn là supermask của m, có đúng 2^{superCnt[m]}-1 cách. Công thức bao hàm-loại trừ cho phần bù của hợp chính là tổng với dấu theo parity của m, nên thuật toán đếm đúng các tập có AND bằng 0.
Độ phức tạp: O(n + 20·2^20) thời gian và O(2^20+n) bộ nhớ.