#include <iostream>
#include <algorithm>
using namespace std;
int n,k;
int num[25];
int x[25];  
int sum=0;
int cnt=0;

bool gc(int x) {  //判断质数
    if(x==1||x==0) {
        return false;
    } else if(x%2==0) {
        return false;
    }
    for(int i=3; i<x/2; i+=2) {
        if(x%i==0) {
            return false;
        }
    }
    return true;
}
bool bd(int a) { 
    if(x[a]<=x[a-1]) {
        return false;
    } else if(a<k&&num[n]==x[a]) {
        return false;
    }
    return true;
}

void DFS(int a) {
    if(a>k) {

        if(gc(sum)) {
            cnt++;
        }
        return ;
    }
    for(int i=1; i<=n; i++) {
        sum=0;
        for(int j = 1; j<a; j++) {
            sum+=x[j];
        }
        x[a]=num[i];
        sum+=x[a];
        if(bd(a))
        {
            sum+=x[i];
            DFS(a+1);
            sum-=x[i];
        }
    }
}

int main() {
    cin >> n>>k;
    for(int i=1; i<=n; i++) {
        cin >> num[i];
    }
    sort(num,num+n);
    DFS(1);
    cout << cnt<< endl;
    return 0;
}