Fibonacci3

#include <bits/stdc++.h>
using namespace std;
ifstream fin ("fibonacci3.in");
ofstream fout ("fibonacci3.out");
typedef unsigned long long ull;
const int mod = 100003, N = 26;
int n, x[N];
ull a[N], ans;
vector <ull> H[mod + 1];

void Insert(ull val)
{
    ull key = val % mod;

    for (auto it : H[key])
        if (it == val)
            return;
    H[key].push_back(val);
}

bool FindHash(ull val)
{
    ull key = val % mod;

    for (auto it : H[key])
        if (it == val)
            return 1;
    return 0;
}

void Back(int k, ull sum)
{
    for (int i = x[k - 1] + 1; i <= n; i++)
    {
        x[k] = i;

        if (FindHash(sum + a[i]))
            ans++;

        if (k < n)
            Back(k + 1, sum + a[i]);
    }
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i];

    H[0].push_back(0);
    ull a = 0, b = 1, c;
    for (; ULLONG_MAX - b >= a;)
    {
        c = a + b;
        a = b;
        b = c;
        Insert(c);
    }

    Back(1, 0);

    fout << ans;
    return 0;
}