#pragma region Macros #include #define rep(i, n) for(int(i) = 0; (i) < (n); (i)++) #define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++) #define ALL(v) (v).begin(), (v).end() #define LLA(v) (v).rbegin(), (v).rend() #define SZ(v) (int)(v).size() #define INT(...) \ int __VA_ARGS__; \ read(__VA_ARGS__) #define LL(...) \ ll __VA_ARGS__; \ read(__VA_ARGS__) #define DOUBLE(...) \ double __VA_ARGS__; \ read(__VA_ARGS__) #define CHAR(...) \ char __VA_ARGS__; \ read(__VA_ARGS__) #define STRING(...) \ string __VA_ARGS__; \ read(__VA_ARGS__) #define VEC(type, name, size) \ vector name(size); \ read(name) #define VEC2(type, name, height, width) \ vector> name(height, vector(width)); \ read(name) using namespace std; using ll = long long; using pii = pair; using pll = pair; using Graph = vector>; template struct edge { int from, to; T cost; edge(int f, int t, T c) : from(f), to(t), cost(c) {} }; template using WGraph = vector>>; const int INF = 1 << 30; const ll LINF = 1LL << 60; const int MOD = 1e9 + 7; const char newl = '\n'; template inline vector make_vec(size_t a, T val) { return vector(a, val); } template inline auto make_vec(size_t a, Ts... ts) { return vector(a, make_vec(ts...)); } void read() {} template inline void read(T &a) { cin >> a; } template inline void read(pair &p) { read(p.first), read(p.second); } template inline void read(vector &v) { for(auto &&a : v) read(a); } template inline void read(Head &head, Tail &...tail) { read(head), read(tail...); } template void write(const T &a) { cout << a << '\n'; } template void write(const vector &a) { for(int i = 0; i < a.size(); i++) cout << a[i] << (i + 1 == a.size() ? '\n' : ' '); } template void write(const Head &head, const Tail &...tail) { cout << head << ' '; write(tail...); } template void writel(const T &a) { cout << a << '\n'; } template void writel(const vector &a) { for(int i = 0; i < a.size(); i++) cout << a[i] << '\n'; } template void writel(const Head &head, const Tail &...tail) { cout << head << '\n'; write(tail...); } template auto sum(const vector &a) { return accumulate(ALL(a), T(0)); } template auto min(const vector &a) { return *min_element(ALL(a)); } template auto max(const vector &a) { return *max_element(ALL(a)); } template inline void chmax(T &a, T b) { (a < b ? a = b : a); } template inline void chmin(T &a, T b) { (a > b ? a = b : a); } struct IO { IO() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); } } io; #pragma endregion int main() { INT(n, k); VEC(int, a, n); sort(ALL(a)); const int M1 = 998244353, M2 = 1e9 + 7, M3 = 1e9 + 9; using tp = tuple; set se; for(int bit = 0; bit < (1 << n); bit++) { if(__builtin_popcount(bit) < k) continue; tp tpsum = {0, 0, 0}, tpprod = {1, 1, 1}; rep(i, n) { if(bit & (1 << i)) { get<0>(tpsum) += a[i]; get<1>(tpsum) += a[i]; get<2>(tpsum) += a[i]; get<0>(tpprod) = get<0>(tpprod) * a[i] % M1; get<1>(tpprod) = get<1>(tpprod) * a[i] % M2; get<2>(tpprod) = get<2>(tpprod) * a[i] % M3; } } se.insert(tpsum); se.insert(tpprod); } write(se.size()); }