Cho n số nguyên không âm ~a_1, a_2, ..., a_n~. Ta gọi dãy chỉ số ~i_1, i_2, ..., i_k (1 ≤ i_1< i_2 < ... < i_k ≤ n)~ là một nhóm gồm ~k~ số.

Yêu cầu: Đếm số nhóm thoả mãn ~a_{i1}~ & ~a_{i2}~ & ... & ~a_{ik} = 0 (1 ≤ k ≤ n)~ ?

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương ~n (1 ≤ n ≤ 10^6)~.
• Dòng thứ hai chứa n số nguyên ~a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^6)~.

Kết quả ra: In ra phần dư của kết quả tìm được khi chia cho ~1000000007 (10^9 + 7)~.

Ví dụ:

INPUT

4
0 1 2 3

OUTPUT

10