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
#include <iostream>
#include <list>
//#include <cmath>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

using namespace std;

unsigned long long int DwaDoPotegi(unsigned long long int potega){
	unsigned long long int wynik=1;
	for(unsigned long long int i=0; i<potega; ++i){
		wynik*=2;
		while(wynik>=1000000007){
			wynik-=1000000007;
		}
	}
	return wynik;
}

/*Autor: Agnieszka Klich*/

int main(int argc, char** argv) {
	
//	cout << DwaDoPotegi(5000)<< endl;
	
	unsigned long long liczbaOpakowan, liczbaCukierkow;
	list<unsigned long long int> listaOpakowan;
	
	cin >> liczbaOpakowan;
	for(unsigned long long int i=0; i<liczbaOpakowan; ++i){
		cin >> liczbaCukierkow;
		listaOpakowan.push_back(liczbaCukierkow);
	}
	listaOpakowan.sort();
	
	unsigned long long int potega2=1;
	unsigned long long int ile = 0;
	unsigned long long int wynik = 0;
	unsigned long long int ileTeraz = 1;
	unsigned long long int mnoznik = 1;
	unsigned long long int ktory = 0;
	
	for(list<unsigned long long int>::iterator it = listaOpakowan.begin(); it!=listaOpakowan.end(); ){
		ile=0;
		while(*it<=potega2 && it!=listaOpakowan.end()){
//			cout << "licze: " << *it << endl;
			++ile;
			it++;
			++ktory;
		};
		potega2 =DwaDoPotegi(ktory);

		
		if(ile==0) {
			cout << wynik <<"\n";
			return 0;
		}
		ileTeraz = (DwaDoPotegi(ile)-1) * mnoznik;
		wynik += ileTeraz;
		
//		cout << "ileteraz: " << ileTeraz << " ile: " << ile << " wynik: " << wynik << " mnoznik: " << mnoznik << " potega2: "<<potega2<<endl;
		mnoznik*=ileTeraz;
		
		while(mnoznik>=1000000007){
			mnoznik-=1000000007;
		}
		
		while(wynik>=1000000007){
			wynik-=1000000007;
		}

	}
	cout << wynik <<"\n";
	return 0;
}