#include <bits/stdc++.h>
using namespace std;
const int N = 5e6+10;

int n,k;
int a[30];

vector<bool> isp;

void pre() {
	isp.resize(1.5e8);
	fill(isp.begin(), isp.end(), true);
	
	for(int p=2;p<=1.25e8;p++) {
		if(!isp[p])
			continue;
			
		for(int q=2;p*q<=1.25e8;q++) {
			isp[p*q] = false;
		}
	}
}

bool isprime(int x) {
	return isp[x];
}

int ans[30], ans2=0;

void dfs(int p, int last) {
	if(p == k+1) {
		int sum = 0;
		for(int i=1;i<=k;i++) {
			sum += a[ans[i]];
		}
		
		if(isprime(sum))
			ans2++;
		
		return;
	}
	
	for(int i=last+1;i<=n;i++) {
		ans[p] = i;
		dfs(p+1, i);
	}
}

int main() {
	pre();
	
	cin>>n>>k;
	
	for(int i=1;i<=n;i++) {
		cin>>a[i];
	}
	
	dfs(1, 0);
	
	cout<<ans2;
	
    return 0;
}

#include <iostream>
using namespace std;

int num[20];
int ans = 0;

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

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

int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; ++i)
    {
        cin >> num[i];
    }
    ans = 0;
    dfs(0, 0, 0, n, k);
    cout << ans << endl;
    return 0;
}