1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
using namespace std;

#define P 14
int n;
int t[5002];
int p2[P];
int c[P];
int w[5002];

// int sier[5001][5001];

int main() {

	// sierpinki mod 10^9 +7
	int mod = 1000000007;
	// sier[0][0] = 1;

	// for(int i=1; i<=5000; i++) {
	// 	sier[i][i] = 1;
	// 	sier[i][0] = 1;
	// }

	// for(int i=1; i<=5000; i++) {
	// 	for(int j=1; j<i;j++) {
	// 		sier[i][j] = (sier[i-1][j] + sier[i-1][j-1]) % mod;
	// 	}	
	// }


	// for(int i=0; i<=15; i++) {
	// 	for(int j=0; j<=15;j++) {
	// 		printf("%d ", sier[i][j]);
	// 	}	printf("\n");
	// }

	// printf("10 po 4 = %d\n", sier[10][4]);
	// printf("34 po 12 = %d\n", sier[34][12]);


	scanf("%d", &n);
	for (int i = 0; i < n; ++i) w[i]=0;
	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &t[i]);
	}

	p2[0] = 1;
	c[0] = 0;
	for (int i = 1; i < P; ++i)
	{
		p2[i] = (p2[i-1] * 2) % mod;
		c[i] = 0;
		// printf("%d\n", p2[i]);
	}

	// zlicz potego2; 
	for(int i=0;i<n;i++) {
		bool isp = false;
		for (int j=0;j<=13;j++) {
			if(t[i] == p2[j]) {
				c[t[i]]++;
				isp = true;
				break;
			}
		}
		if(!isp) w[t[i]]++;
	}

	// printf("Zliczone p2: ");
	// for (int i = 0; i < 10; ++i)
	// {
	// 	printf("(%d: %d) ", i, c[i]);
	// } printf("\n");


	// printf("Zliczone nie p2: ");
	// for (int i = 0; i < 10; ++i)
	// {
	// 	printf("(%d: %d) ", i, w[i]);
	// } printf("\n");
	
	int result = 0;
	for (int i = 0; i < P; ++i)
	{
		// printf("Zaczynamy dla %d\n", p2[i]);
		int int_res = 1;
		bool koniec = false;
		for(int j=0; j<=i; j++) {
			int pot = p2[j];
			if(c[pot] == 0) {
				// printf("Brakuje %d!\n", pot);
				koniec = true;
			} else {
				int_res *= (p2[c[pot]]-1);
				// printf("int_res * 2^%d-1\n", c[pot]);
			}
		}
		if(koniec) break;

		int wyk = 0;
		for(int j=1; j<p2[i+1];j++) {
			wyk+= w[j];
		}
		// printf("result * 2^%d\n", wyk);
		if (wyk != 0) {
			int_res += (int_res * (p2[wyk] - 1)) % mod;
		}
		// printf("int_res: %d\n", int_res);

		result = (result + int_res) % mod;
	}
	
	printf("%d\n", result);

	return 0;
}