using namespace std;
#ifdef EZ
#include "./ez/ez.h"
const string FILE_NAME = "test";
#else
#include <bits/stdc++.h>
const string FILE_NAME = "indep";
#endif
#define mp make_pair
#define ll long long
#define pb push_back
#define fi first
#define se second
#define cin fin
#define cout fout
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");
// indentare cu 2 spatii pentru ca sursa cu 3 spatii trece de 10KB =[
class big_int
{
private:
int sign; // -1 daca numarul este negativ, +1 daca este pozitiv
string digits; // cifrele numarului, stocate in ordine inversa
public:
// initializare implicita cu 0
big_int()
{
digits = "0";
sign = 1;
}
// initializare prin intermediul unui sir de caractere
big_int(string s)
{
int i;
if (s.front() == '-')
sign = -1, i = 1;
else if (s.front() == '+')
sign = 1, i = 1;
else
sign = 1, i = 0;
for (int j = s.size() - 1; j >= i; --j)
digits.push_back(s[j]);
}
// initializare prin intermediul unui caracter
big_int(char c)
{
sign = 1;
digits.push_back(c);
}
// initializare prin intermediul unui numar intre -2^31 si 2^31 - 1
big_int(int n)
{
if (n < 0)
sign = -1;
else
sign = 1;
n = std::abs(n);
do {
digits.push_back(n%10 + '0');
n /= 10;
} while (n);
}
// conversie la sir de caractere
operator string() const
{
string ans;
if (sign == -1)
{
ans.resize(1 + digits.size());
ans.front() = '-';
reverse_copy(digits.begin(), digits.end(), ans.begin() + 1);
return ans;
}
else
{
ans.resize(digits.size());
reverse_copy(digits.begin(), digits.end(), ans.begin());
return ans;
}
}
// comparator ==
friend bool operator == (const big_int& a, const big_int& b)
{
return (a.sign == b.sign && a.digits == b.digits);
}
// comparator <
friend bool operator < (const big_int& a, const big_int& b)
{
if (a.sign == -1 && b.sign == 1)
return true;
if (a.sign == 1 && b.sign == -1)
return false;
if (a.sign == -1 && b.sign == -1)
return (b.abs() < a.abs());
if (a.sign == 1 && b.sign == 1)
{
if (a.digits.size() < b.digits.size())
return true;
if (a.digits.size() > b.digits.size())
return false;
for (int i = a.digits.size() - 1; i >= 0; --i)
if (a.digits[i] < b.digits[i])
return true;
else if (a.digits[i] > b.digits[i])
return false;
return false;
}
}
// comparator <=
friend bool operator <= (const big_int& a, const big_int& b)
{
return (a < b || a == b);
}
// comparator >=
friend bool operator >= (const big_int& a, const big_int& b)
{
return !(a < b);
}
// valoarea absoluta
big_int abs() const
{
big_int ans = *this;
ans.sign = 1;
return ans;
}
// opusul (inversul in raport cu adunarea)
big_int operator - () const
{
if (digits == "0")
return *this;
big_int ans = *this;
ans.sign *= -1;
return ans;
}
// suma a 2 numere
big_int operator + (const big_int& b) const
{
if (sign == -1 && b.sign == -1)
return -(this->abs() + b.abs());
if (sign == -1 && b.sign == 1)
return b - this->abs();
if (sign == 1 && b.sign == -1)
return *this - b.abs();
if (sign == 1 && b.sign == 1)
{
big_int ans;
ans.sign = 1;
ans.digits = "";
int cnt = 0, i;
for (i = 0; i < std::min(digits.size(), b.digits.size()); ++i)
{
int sum = digits[i]-'0' + b.digits[i]-'0' + cnt;
ans.digits.push_back(sum%10 + '0');
cnt = sum/10;
}
for (; i < digits.size(); ++i)
{
int sum = digits[i]-'0' + cnt;
ans.digits.push_back(sum%10 + '0');
cnt = sum/10;
}
for (; i < b.digits.size(); ++i)
{
int sum = b.digits[i]-'0' + cnt;
ans.digits.push_back(sum%10 + '0');
cnt = sum/10;
}
for (; cnt; cnt /= 10)
ans.digits.push_back(cnt%10 + '0');
return ans;
}
}
// diferenta a 2 numere
big_int operator - (const big_int& b) const
{
if (sign == -1 && b.sign == -1)
return b.abs() - this->abs();
if (sign == -1 && b.sign == 1)
return -(this->abs() + b);
if (sign == 1 && b.sign == -1)
return *this + b.abs();
if (sign == 1 && b.sign == 1)
{
if (*this < b)
return -(b - *this);
big_int ans;
ans.sign = 1;
ans.digits = "";
int i;
bool cnt = 0;
for (i = 0; i < std::min(digits.size(), b.digits.size()); ++i)
{
if ((digits[i]-'0') - (b.digits[i]-'0') - cnt < 0)
{
ans.digits.push_back((digits[i]-'0') - (b.digits[i]-'0') - cnt + 10 + '0');
cnt = 1;
}
else
{
ans.digits.push_back((digits[i]-'0') - (b.digits[i]-'0') - cnt + '0');
cnt = 0;
}
}
for (; i < digits.size(); ++i)
{
if ((digits[i]-'0') - cnt < 0)
{
ans.digits.push_back((digits[i]-'0') - cnt + 10 + '0');
cnt = 1;
}
else
{
ans.digits.push_back((digits[i]-'0') - cnt + '0');
cnt = 0;
}
}
while (ans.digits.size() != 1 && ans.digits.back() == '0')
ans.digits.pop_back();
return ans;
}
}
// produsul a 2 numere
big_int operator * (const big_int& b) const
{
if (*this == big_int(0) || b == big_int(0))
return big_int(0);
big_int ans;
if (sign + b.sign == 0)
ans.sign = -1;
else
ans.sign = 1;
ans.digits.resize(digits.size() + b.digits.size(), '0');
int cnt, i, j;
for (i = 0; i < digits.size(); ++i)
{
cnt = 0;
for (j = 0; j < b.digits.size(); ++j)
{
int sum = (ans.digits[i+j]-'0' + (digits[i]-'0') * (b.digits[j]-'0') + cnt);
ans.digits[i+j] = sum%10 + '0';
cnt = sum/10;
}
if (cnt)
ans.digits[i+j] = (ans.digits[i+j]-'0' + cnt) + '0';
}
while (ans.digits.size() != 1 && ans.digits.back() == '0')
ans.digits.pop_back();
if (ans.digits == "0")
return big_int(0);
return ans;
}
// catul impartirii a 2 numere
big_int operator / (const big_int& b) const
{
if (*this == big_int(0))
return big_int(0);
big_int ans, A = this->abs(), B = b.abs();
if (A < B)
return big_int(0);
big_int dei, inm;
dei.digits = "";
ans.digits = "";
int i;
for (i = digits.size() - 1; ; --i)
{
dei.digits.insert(dei.digits.begin(), digits[i]);
if (dei >= B)
break;
}
for (i--; i >= -1; --i)
{
for (int j = 0; j <= 9; ++j)
{
inm.digits[0] = j+'0';
if ( !(B * inm <= dei) )
{
inm.digits[0]--;
break;
}
}
ans.digits.push_back(inm.digits[0]);
dei = dei - B*inm;
if (dei.digits == "0")
dei.digits = "";
if (i >= 0)
dei.digits.insert(dei.digits.begin(), digits[i]);
}
if (sign + b.sign == 0)
ans.sign = -1;
else
ans.sign = 1;
reverse(ans.digits.begin(), ans.digits.end());
return ans;
}
// restul impartirii a 2 numere pozitive
big_int operator % (const big_int& b) const
{
return *this - *this / b * b;
}
// citire prin intermediul stream-urilor
friend istream& operator >> (istream& in, big_int& n)
{
int i;
string nr;
in >> nr;
if (nr.front() == '-')
n.sign = -1, i = 1;
else if (nr.front() == '+')
n.sign = 1, i = 1;
else
n.sign = 1, i = 0;
if (nr == "-0")
n.sign = +1;
n.digits.resize(nr.size() - i);
reverse_copy(nr.begin() + i, nr.end(), n.digits.begin());
return in;
}
// scriere prin intermediul stream-urilor
friend ostream& operator << (ostream& out, const big_int& n)
{
if (n.sign == -1)
out << '-';
for (int i = n.digits.size() - 1; i >= 0; --i)
out << n.digits[i];
return out;
}
};
big_int fact[501];
void genFact()
{
fact[0] = 1;
for (int i = 1; i <= 500; ++i)
fact[i] = fact[i-1] * i;
}
big_int comb(int n, int k)
{
if (n < k) return big_int(0);
return fact[n] / fact[k] / fact[n-k];
}
char M[1001];
void genMobius()
{
M[1] = 1;
for (int i = 1; i <= 1000; ++i)
for (int j = i+i; j <= 1000; j += i)
M[j] -= M[i];
}
int n;
int v[501];
int fv[1001], nr[1001];
int main()
{
genFact();
genMobius();
cin >> n;
for (int i = 1; i <= n; ++i) cin >> v[i], fv[v[i]]++;
for (int d = 1; d <= 1000; ++d)
for (int i = d; i <= 1000; i += d)
nr[d] += fv[i];
big_int ans = 0;
for (int d = 1; d <= 1000; ++d)
for (int len = 1; len <= n; ++len)
ans = ans + comb(nr[d], len) * (int) M[d];
cout << ans;
}