Problem: 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

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>

constexpr long long int MOD = 1000000007;
long long int power(long long int base, int exp) {
	switch (exp) {
	case 0: return 1;
	case 1: return base % MOD;
	default: return power(base * base % MOD, exp / 2) * power(base, exp % 2) % MOD;
	}
}
long long int power_set_size(int size) {
	static std::vector<long long int> memo(100001, -1);
	if (memo[size] >= 0) return memo[size];
	return memo[size] = power(2, size);
}
long long int calc(const std::vector<int>& values, int size = 20) {
	if (size == 0) return  (power_set_size(values.size()) + MOD - 1) % MOD;
	if (values.empty()) return 0;
	long long int sum{ 0 };
	std::vector<int> sub;
	for (auto i = 0; i < size; ++i) {
		sub.clear();
		for (const auto v : values) if ((v & (1 << i)) != 0) sub.push_back(v);
		sum += calc(sub, i);
	}
	return ((power_set_size(values.size()) + MOD - 1 - sum) % MOD + MOD) % MOD;
}
int count_bit(int n) {
	return (n == 0) ? 0 : (n & 1) + count_bit(n >> 1);
}
int main() {
	int n; std::cin >> n;
	std::vector<int> values(n); for (auto& a : values) std::cin >> a;
	std::vector<long long int> pattern(1 << 20, 0);
	for (const auto a : values) pattern[a]++;
	for (auto i = 0; i < 20; ++i) {
		for (auto j = 0; j < pattern.size(); ++j) 
			if ((j & (1 << i)) == 0) {
				pattern[j] += pattern[j | (1 << i)];
				pattern[j] %= MOD;
			}
	}
	long long int result = 0;
	for (auto i = 0; i < pattern.size(); ++i) {
		if (count_bit(i) % 2 == 0) {
			result += power(2, pattern[i]) - 1;
		}
		else {
			result -= power(2, pattern[i]) - 1;
		}
		result %= MOD;
	}
	std::cout << (result + MOD) % MOD << std::endl;
}