Jzzhu và những con số

Cho $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$.

Một nhóm kích thước $k$ là một dãy chỉ số $i_1<i_2<\cdots <i_k$ (với $1\le k\le n$). Hãy đếm số nhóm sao cho phép AND theo bit của tất cả các phần tử trong nhóm bằng $0$:

$$a_{i_1}<mrow><mi>\&</mi></mrow>a_{i_2}<mrow><mi>\&</mi></mrow>\cdots <mrow><mi>\&</mi></mrow>a_{i_k}=0.$$

In ra kết quả theo modulo ${10}^9+7$.

Ở đây $x<mrow><mi>\&</mi></mrow>y$ là phép AND theo bit của hai số $x$ và $y$.

Dữ liệu vào

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

Dữ liệu ra

• Một số nguyên duy nhất: số nhóm thỏa mãn, lấy theo modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^6$
• $0\le a_i\le {10}^6$

Ví dụ