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
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int paczki[5002];
long long suma1[5000*5000];
long long suma2[5000*5000];
int maxsuma=5000*5000;
long long wynik;
int maxpaczka= 5001;

long long mod = 1000000007;
int main(){


	int n;
	cin >>n;

	for(int i=0;i<n;i++) {
		cin >> paczki[i];
		//cout << paczki[i];
	}
	sort(paczki, paczki + n);

	suma1[0]=1;
//	if (paczki[0]==1) suma[paczki[0]=1;
//	else { cout<<"0"<<endl; return 0;}

	int paczka;
	long long temp;
	long long sumakolejnych=0;

	for (int i=0;i<n;i++) {
		paczka = paczki[i];
		sumakolejnych+=paczka;
		for(int j=paczka-1;j<=maxpaczka;j++) {
			temp = suma1[j];
//			cout << "j="<< j<< " suma1[j]=" << temp;
			if(j+paczka>=maxpaczka)
				suma2[maxpaczka] =(suma2[maxpaczka]+temp)%mod;
			else
				suma2[j + paczka] += temp;
//			cout <<" suma1[j + paczka]=" << suma1[j + paczka]  << " paczka= " << paczka <<endl;

		}
//		cout<<endl;
		for(int j=0;j<=maxpaczka;j++){
			suma1[j]=(suma1[j]+suma2[j])%mod;
			suma2[j]=0;
		}
	}
	for(int i=1;i<=maxpaczka;i++) {
		wynik=(wynik+suma1[i])%mod;
	
	}
//	cout <<sumakolejnych << "!\n";
	cout <<wynik<<endl;

	return 0;






}