Đề bài Hoàng có ~n~ số nguyên không âm a{~1~}, a{~2~}, …, a_{~n~}.

Ta gọi một dãy chỉ số i{~1~}, i{~2~}, …, i{~k~} (~1~ ≤ i{~1~} < i{~2~} < … < i{~k~} ≤ ~n~) là một nhóm có kích thước ~k~.

Hoàng muốn biết có bao nhiêu nhóm tồn tại sao cho:

a{~i~_~1~} & a{~i~_~2~} & … & a_{~i~_~k~} = ~0~

với mọi ~1~ ≤ ~k~ ≤ ~n~.

Hãy giúp Hoàng tìm ra số nhóm như vậy và in kết quả theo modulo ~1000000007~ (~10~^{~9~} + ~7~). ( Điều này có nghĩa là sau khi bạn tính được số nhóm, bạn lấy kết quả chia cho ~1000000007~ và in ra phần dư .)

Ký hiệu ~x~ & ~y~ biểu thị phép AND theo bit của hai số nguyên ~x~ và ~y~.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ (1 ≤ ~n \le 10^{6~}).
• Dòng thứ hai chứa ~n~ số nguyên a{1}, a{2}, …, a{n} (0 ≤ a{i} ≤ 10^{6}).

Output

In ra một số nguyên duy nhất — số nhóm thỏa mãn điều kiện, theo modulo 1000000007 (10^{9} + 7).

Sample input

3
2 3 3

Sample ouput

0

Sample input

4
0 1 2 3

Sample output

10

Sạmple input

6
5 2 0 5 2 1

Sample output

53