#include<iostream>
#include<cstring>
using namespace std;

int n, a[100005], s[100005];
long long dp[100005];
const long long MAXN=1e9+9;

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s[i] = s[i-1] + a[i];
	}
	
	memset(dp, 0, sizeof(dp));
	dp[0] = 1;
	for(int i = 1; i <= n; i++)
		for(int j = i; j >= 1; j--) //最后一组是j…i
			if(dp[j-1] != -1 && s[i] - s[j-1] >= 0)
				{
					dp[i] += dp[j-1];
					dp[i]%=MAXN;
				}
	cout << dp[n]%MAXN << endl;
	
	return 0;
}