#include<bits/stdc++.h>
using namespace std;
const int N=10086;
int ac,n;
int a[N],shu[N];
bool b[N];
bool prime(int x)
{
	for(int i=2;i*i<=x;i+=6)
	{
		if(x%i==0 or x%(i+2)==0) return false;
	}
	ac++;
}
void dfs(int k)
{
	for(int i=1;i<=n;i++)
	{
		if(b[i]==0&&i>a[k-1])
		{
			a[k]=i;
			b[i]=1;
			if(k==n)
			{
				int ans=0;
                for(int i=1;i<=n;i++) ans+=shu[a[i]];
                prime(ans);
			}
			else dfs(k+1);
			a[k]=0;
			b[i]=0;			
		}
	}
}
int main()
{
    int k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>shu[i];
    dfs(1);
    cout<<ac;
    return 0;
}