# a136: P-1-7. 子集合乘積
##### link: https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a136
###### tags: `APCS` `recursion`
* 列舉全部組合
* 這裡學習他的列舉方式，比較簡潔

#include <bits/stdc++.h>

using namespace std;

int n;
const int p=10009;
int ans=0;

void backtrack(vector<int> &table,int layers,long long int sum){
    if (layers>=n){
        if (sum==1) ans++;
        return;
    }
    backtrack(table,layers+1,(sum*table[layers])%p);
    backtrack(table,layers+1,sum);
    
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    vector<int> table(n);
    for (int i=0;i<n;i++){
        cin>>table[i];
    }
    long long int sum=1;
    backtrack(table,0,sum);
    cout<<ans-1;
    return 0;
}