本题是组合回溯（dfs)的入门题
区分组合回溯和排列回溯的使用
#include<bits/stdc++.h>
using namespace std;
#define int long long
/* 开始学习组合枚举+回溯---本质就是暴力DFS 
   1：明确你的dfs的含义（利用上下层实现本层）《----为了实现这个含义你要啥参数随便
   2：起点与终点
   3:三大注意：可选？重复？越界？ 
  ================================================
  okok 回到本题：n个数 选k个+ sum==质数的个数 
  ===================================
  okok 学到dfs的精髓了：我们之前的随意暴力选举本质是排列（n!)
                        但是本题仅是组合--（cn,m)
		如果使用排列一定一定会爆
  讲讲如何进行组合排序：多一个start 让每次下层枚举都有个开头（不重复枚举）						 
*/
const int N=25;
int a[N];
bool f[N];
int n,k;
int ans;
bool is_prime(int x)//是返回1 
{
  if(x<2) return 0;	
  for(int i=2;i<=x/i;i++)
   if(x%i==0) return 0;
  return 1; 
}
//组合枚举 
void dfs(int t,int sum,int start)
{
	//终点
	if(t==k)
	{
	  if(is_prime(sum))ans++;
	  return;	
	}
	else
	for(int i=start;i<n;i++)
	{
	  if(!f[i])
	  {
	    f[i]=1;
		dfs(t+1,sum+a[i],i+1);
		f[i]=0;	
	  }	
	} 
}

//排列枚举 
//void dfs(int t,int sum)//当前选了几个数，当前的sum 
//{
//  //终点
//  if(t==k)
//  {
//    if(is_prime(sum)) ans++;
//	return; 	
//  }	
//  //遍历
//  else
//  for(int i=0;i<n;i++)
//  {
//  	if(!f[i])//没选过 
//	  {
//	  	f[i]=1;
//		dfs(t+1,sum+a[i]);
//		f[i]=0;//回溯   
//	  } 
//  } 
//  return;
//}
signed main()
{ std::ios::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
    cin>>n>>k;
	for(int i=0;i<n;i++) cin>>a[i];
    dfs(0,0,0);
	cout<<ans<<"\n";		
	return 0;
}