dfs mle

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxx = 5e8;
int n, m, k[30],cnt,p[100001];
bool prime[maxx];
void isprime(int x)
{
	for (int i = 2; i <= x; i++)
	{
		if (!prime[i]) p[++cnt] = i;
		for (int j = 1; j <= cnt && p[j] * i <= x; j++)
		{
			prime[i * p[j]] = 1;
			if(i % p[j] == 0)
				break;
		}
	}
}
int ans[30],q;
void dfs(int x)
{
	if (x == m + 1)
	{
		int sum = 0;
		for (int i = 1; i <= m; i++)
		{
			sum += ans[i];
		}
		if (!prime[sum])
		{
			q++;
		}
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (ans[x - 1] >= k[i] && x!=1)
			continue;
		ans[x] = k[i];
		dfs(x + 1);
		ans[x] = 0;
	}
}

signed main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> k[i];
	isprime(maxx);
	sort(k + 1, k + n + 1);
	dfs(1);
	cout << q;
	return 0;
}