#include<bits/stdc++.h>
using namespace std;
const int N=1e7+1;
int n,b[21],k,ans=0;
bool a[N];
void dfs(int h,int sum,int m)
{
	if(h>k) return ;
	
	for(int i=m;i<n;i++)
	{
		dfs(h+1,sum+b[i],m+1);
	}
	if(a[sum]==0&&h==k)
	{
		ans++;
		return ;
	}
}
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>b[i];
	}
	for(int i=2;i<N;i++)
	{
		if(a[i]!=1)
		{
			for(int j=2;j*i<N;j++)
			{
				a[j]=1;
			}
		}
	}
	dfs(0,0,0);
	cout<<ans;
    return 0;
}