#include <bits/stdc++.h>
using namespace std;
int n, k, cnt = 0;
vector<int> numbers;
bool isPrime(int num) {
    if (num <= 1) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0)
            return false;
    }
    return true;
}
void generateCombinations(int start, int sum, int count) {
    if (count == k) {
        if (isPrime(sum))
            cnt++;
        return;
    }
    if (n - start < k - count) return;
    
    for (int i = start; i < n; i++) {
        generateCombinations(i + 1, sum + numbers[i], count + 1);
    }
}
int main() {
    cin >> n >> k;
    numbers.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
    }
    
    generateCombinations(0, 0, 0);
    cout << cnt << endl;
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n,k,cnt = 0;
vector<int>numbers;

bool isPrime(int num)
{
  if(num<=1) return false;
  for(int i = 2;i*i<=num;i++)
  {
    if(num%i == 0)
    return false;
  }
  return true;
}

void generateCombinations(int start,int sum,int count)
{
  if(count == k)
  {
    if(isPrime(sum))
    cnt++;
    return ;
  }
  for(int i = start;i<n;i++)
  {
    generateCombinations(i+1,sum+numbers[i],count+1);
  }
}

int main()
{
  cin>>n>>k;
  numbers.resize(n);
  for(int i = 0;i<n;i++)
  {
    cin>>numbers[i];
  }
  generateCombinations(0,0,0);
  cout << cnt << endl;
  return 0;
}

#include<bits/stdc++.h> using namespace std; int n, k;

int read(){ int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9'){ if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x * f; }

int a[12001];

bool pd(int k){ for (int i = 2;i * i <= k;i ++) if (k % i == 0) return 0; return 1; }

int s;

void dfs(int x, int y, int z){ if (x == k && pd(y)){ ++ s; return ; } for (int i = z;i < n;i ++) dfs(x + 1, y + a[i], i + 1); return ; }

int main() { n = read(), k = read(); for (int i = 0;i < n;i ++)a[i] = read(); dfs (0, 0, 0); printf("%d\n", s); return 0; }