Zero AND Subsets

Zero AND Subsets

Given a multiset of nonnegative integers a_1, a_2, .., a_N.

How many non-empty subsets of this set have a value bitwiseAND of 0?

Find the remainder of the answer divided by 10 ^ 9 + 7.

input

N a_1 a_2 ... a_N

output

Divide the answer by 10 ^ 9 + 7 and output the remainder.

Constraint

• 1 \ leq N \ leq 10 ^ 5
• 0 \ leq a_i \ leq 2 ^ {20} -1

Input example

6 8 6 9 1 2 1

Output example

51

Example

Input

6 8 6 9 1 2 1

Output

51

inputFormat

input

N a_1 a_2 ... a_N

outputFormat

output

Divide the answer by 10 ^ 9 + 7 and output the remainder.

Constraint

• 1 \ leq N \ leq 10 ^ 5
• 0 \ leq a_i \ leq 2 ^ {20} -1

Input example

6 8 6 9 1 2 1

Output example

51

Example

Input

6 8 6 9 1 2 1

Output

51

样例

6
8 6 9 1 2 1

51