#include #include typedef unsigned long long ULLONG; typedef long long LLONG; static const LLONG MOD_NUM = 1000000007LL; //998244353LL; static const LLONG INF_NUM = LLONG_MAX; template static void get(_T& a) { std::cin >> a; } template static void get(_T& a, _T& b) { std::cin >> a >> b; } template static void get(_T& a, _T& b, _T& c) { std::cin >> a >> b >> c; } template static _T tp_abs(_T a) { if (a < (_T)0) { a *= (_T)-1; } return a; } template void tp_getPrimes(_T targ, std::map<_T, _T>& primes) { _T target = targ; _T i = 2; while ((i * i) <= target) { if ((target % i) == 0) { target /= i; primes[i]++; } else { i++; } } if (target > 1) { primes[target]++; } } static void task(); int main() { task(); fflush(stdout); return 0; } static void task() { int N, K; get(N, K); std::vector ai(N); for (int i = 0; i < N; i++) { get(ai[i]); } std::set ans; std::set> multiply; for (int select = 0; select < (1 << N); select++) { std::bitset<32> bs(select); if (bs.count() < K) continue; LLONG sum = 0, mul = 1; std::multiset elem; for (int i = 0; i < N; i++) { if (select & (1 << i)) { LLONG s = ai[i]; sum += s; if (s != 1LL) { std::map primes; tp_getPrimes(s, primes); for (auto p : primes) { for (int j = 0; j < p.second; j++) { elem.insert(p.first); } } } mul *= s; if (mul > (1000LL * N)) { mul = MOD_NUM; } } } ans.insert(sum); if (mul == MOD_NUM) { multiply.insert(elem); } else { ans.insert(mul); } } printf("%d\n", (int)ans.size() + (int)multiply.size()); }