#include <bits/stdc++.h> #define all(x) x.begin(), x.end() using i64 = long long; constexpr int P = 1000000009; // assume -P <= x < 2P int norm(int x) { if (x < 0) { x += P; } if (x >= P) { x -= P; } return x; } template<class T> T power(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; } struct Z { int x; Z(int x = 0) : x(norm(x)) {} int val() const { return x; } Z operator-() const { return Z(norm(P - x)); } Z inv() const { assert(x != 0); return power(*this, P - 2); } Z &operator*=(const Z &rhs) { x = i64(x) * rhs.x % P; return *this; } Z &operator+=(const Z &rhs) { x = norm(x + rhs.x); return *this; } Z &operator-=(const Z &rhs) { x = norm(x - rhs.x); return *this; } Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); } friend Z operator*(const Z &lhs, const Z &rhs) { Z res = lhs; res *= rhs; return res; } friend Z operator+(const Z &lhs, const Z &rhs) { Z res = lhs; res += rhs; return res; } friend Z operator-(const Z &lhs, const Z &rhs) { Z res = lhs; res -= rhs; return res; } friend Z operator/(const Z &lhs, const Z &rhs) { Z res = lhs; res /= rhs; return res; } }; template <typename T> struct Fenwick { const int n; std::vector<T> a; Fenwick(int n) : n(n), a(n) {} void add(int x, T v) { for (int i = x + 1; i <= n; i += i & -i) { a[i - 1] += v; } } T sum(int x) { T ans = 0; for (int i = x; i > 0; i -= i & -i) { ans += a[i - 1]; } return ans; } T rangeSum(int l, int r) { return sum(r) - sum(l); } }; void jiangly_fan() { int N; std::cin >> N; std::vector<std::pair<int, int>> A; A.push_back(std::make_pair(0, 0)); for (int i = 1; i <= N; ++i) { int val; std::cin >> val; A.push_back(std::make_pair(A[i - 1].first + val, i)); } // return; std::sort(all(A)); int pref = A[0].first; A[0].first = 1; for (int i = 1; i <= N; ++i) { if (A[i].first == pref) { A[i].first = A[i - 1].first; } else { pref = A[i].first; A[i].first = A[i - 1].first + 1; } } std::sort(all(A), [&](const auto & lhs, const auto & rhs) { return lhs.second < rhs.second; }); int base = 1; while (base < N) { base *= 2; } Fenwick<Z> FW(base); FW.add(A[0].first, 1); for (int i = 1; i <= N; ++i) { Z get = FW.sum(A[i].first + 1); if (i < N) { FW.add(A[i].first, get); } } std::cout << FW.sum(A[N].first + 1).val() << "\n"; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int T = 1; // std::cin >> T; for (int i = 0; i < T; ++i) { jiangly_fan(); } return 0; }