#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr size_t N = 45, K = (1 << 20) + 10;
int n;
int a[N];
ll a1[K], a2[K];
int c1, c2;
ll res;
void calc(int *a, ll v[], int &c, int len)
{
    c = 1;
    for (int i = 1; i <= len; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            v[c + j] = v[j] + a[i];
        }
        c <<= 1;
    }
}
void compute(ll a, ll b)
{
    int l = c2 + 1, r = c2;
    for (int i = 1; i <= c1; i++)
    {
        while (l > 1 && a1[i] + a2[l - 1] >= a)
        {
            l--;
        }
        while (r >= l && a1[i] + a2[r] >= b)
        {
            r--;
        }
        res += r - l + 1;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int l = n >> 1, r = n - l;
    calc(a, a1, c1, l);
    calc(a + l, a2, c2, r);
    ll x = 10000000000;
    for (int k = 9; k >= 0; k--)
    {
        if (k < 9)
        {
            for (int i = 1; i <= c1; i++)
            {
                a1[i] %= x;
            }
            for (int i = 1; i <= c2; i++)
            {
                a2[i] %= x;
            }
        }
        sort(a1 + 1, a1 + c1 + 1);
        sort(a2 + 1, a2 + c2 + 1);
        x /= 10;
        compute(x * 4, x * 5);
        compute(x * 14, x * 15);
    }
    cout << res << '\n';
    return 0;
}