#include <iostream>
using namespace std;
int a[30] , n , k , ans , maxx;
bool un_prime[200000005] ;
void dfs(int step, int num , int x){
    //深搜，step是的第step个数，num是和，x是找了几个数
	if(step == n){//若到了n则每个数都找过了
		if((!un_prime[num]) and x == k)//是不是质数
			ans ++ ;
	}
	else if (x <= k){//若x > k 则不用找了
		dfs(step+1,num+a[step], x + 1);//两种情况
		dfs(step+1,num,x) ;
	}
	
}
int main(){
	cin >> n >> k ;
	for(int i = 0 ; i < n ; i ++){
		cin >> a[i] ;
		maxx += a[i];//最大会是几
	}
	un_prime[0] = un_prime[1] = 1 ;//埃氏筛法(这题貌似暴力寻找质数更快)
	for(int i = 2 ; i <= maxx ; i ++)
		if(!un_prime[i])
			for(int j = i * 2 ; j <= maxx ; j += i)
				un_prime[j] = true ;
	dfs(0,0,0);
	cout << ans ;
	return 0 ;
}

#include <cstdio>
#include <cmath>

int n, k, cnt = 0, x[21];

bool isPrime(int num) {
    if (num <= 1) return false;
    int sqr = (int)sqrt(1.0 * num);
    //如果num没有接近int型变量的范围上界，可以写i*i<=num
    for (int i = 2; i <= sqr; i++) { //遍历2~根号num
        if (num % i == 0) return false;
    }
    return true;
}

void dfs(int index, int nowK, int sum) {
    if (nowK == k) { //选中k个数
        if (isPrime(sum)) { //如果和为素数
            cnt++;
        }
        return;
    }
    if (index == n || nowK > k) { //已经处理完n个数，或者超过k个数，返回
        return;
    }
    //选index号数
    dfs(index + 1, nowK + 1, sum + x[index]);
    //不选index号数
    dfs(index + 1, nowK, sum);
}


int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x[i]);
    }
    dfs(0, 0, 0);
    printf("%d", cnt);
    return 0;
}

点个赞呗！！！