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
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) begin(x), end(x)

using ll =  long long;

ll sum[5000];
int n;
int sweets[5000];

constexpr ll p = 1e9 + 7;                                                                           
                                                                                
#define ra(x) ((x) >= p ? (x)-p : x)                                          
#define rm(x) ((x) % p)              

int main()
{
    fastIO;
    
    sum[0] = 1;

	cin >> n;

    for (int i = 0; i < n; ++i)
    	cin >> sweets[i];
    	//sweets[i]=1;
    	
    sort(sweets, sweets + n);
    
    for (int i = 0; i < n; ++i)
    {
    	/*for (int j = 4999; j >= 4999 - sweets[i]; --j)
    		sum[4999] += sum[j];
    	sum[4999] = rm(sum[4999]);
    	
    	for (int j = 4999 - sweets[i] - 1; j >= sweets[i] - 1; --j)
    		sum[j+sweets[i]] = ra(sum[j+sweets[i]] + sum[j]);*/

        for (int j = 5000 - 1; j >= sweets[i] - 1; --j)
            sum[min(5000-1, j+sweets[i])] = ra(sum[min(5000-1, j+sweets[i])] + sum[j]);
    }
    
    ll ans = 0;
    
    for (int i = 1; i < 5000; ++i)
    	ans += sum[i];
    cout << rm(ans);

    return 0;
}