#include<bits/stdc++.h>
using namespace std;
int n,k,ans,sum;
int a[30];
bool Isprime(int n){
    if(n == 1){
        return false;
    }
    for(int i=2;i*i<=n;i++){
        if(n%i==0)return false;
    }return true;
}
int xunhuan(int k){
    if(k==1){
        for(int b=1;b<=n;b++){
            if(Isprime(a[b]))ans++;
        }
    }
    if(k==2){
        for(int b=1;b<=n;b++){
            for(int c=b+1;c<=n;c++){
                if(Isprime(a[b]+a[c])){
                    ans++;
                }
            }
        }
    }
    if(k==3)
        for(int b=1;b<=n;b++)
            for(int c=b+1;c<=n;c++)
                for(int d =c+1;d<=n;d++)
                    if(Isprime(a[b]+a[c]+a[d]))
                        ans++;
    if(k==4)
        for(int b=1;b<=n;b++)
            for(int c=b+1;c<=n;c++)
                for(int d =c+1;d<=n;d++)
                for(int e = d+1;e<=n;e++)
                    if(Isprime(a[b]+a[c]+a[d]+a[e]))
                        ans++;
    
    if(k==5){
        for(int b=1;b<=n;b++)
        for(int c=b+1;c<=n;c++)
        for(int d=c+1;d<=n;d++)
        for(int e=d+1;e<=n;e++)
        for(int f=e+1;f<=n;f++)
        if(Isprime(a[b]+a[c]+a[d]+a[e]+a[f]))
        ans++;
    }
    if(k==6){
        for(int b=1;b<=n;b++)
        for(int c=b+1;c<=n;c++)
        for(int d=c+1;d<=n;d++)
        for(int e=d+1;e<=n;e++)
        for(int f=e+1;f<=n;f++)
        for(int g=f+1;g<=n;g++)
        if(Isprime(a[b]+a[c]+a[d]+a[e]+a[f]+a[g]))
        ans++;
    }
    if(k==7){
        for(int b=1;b<=n;b++)
        for(int c=b+1;c<=n;c++)
        for(int d=c+1;d<=n;d++)
        for(int e=d+1;e<=n;e++)
        for(int f=e+1;f<=n;f++)
        for(int g=f+1;g<=n;g++)
        for(int h=g+1;h<+n;h++)
        if(Isprime(a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]))
        ans++;
    }
    if(k==8){
        for(int b=1;b<=n;b++)
        for(int c=b+1;c<=n;c++)
        for(int d=c+1;d<=n;d++)
        for(int e=d+1;e<=n;e++)
        for(int f=e+1;f<=n;f++)
        for(int g=f+1;g<=n;g++)
        for(int h=g+1;h<+n;h++)
        for(int i=h+1;i<=n;i++)
        if(Isprime(a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[i]))
        ans++;
    }
    if(k==9){
        for(int b=1;b<=n;b++)
        for(int c=b+1;c<=n;c++)
        for(int d=c+1;d<=n;d++)
        for(int e=d+1;e<=n;e++)
        for(int f=e+1;f<=n;f++)
        for(int g=f+1;g<=n;g++)
        for(int h=g+1;h<+n;h++)
        for(int i=h+1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        if(Isprime(a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[i]+a[j]))
        ans++;
    }
    if(k==10){
        for(int b=1;b<=n;b++)
        for(int c=b+1;c<=n;c++)
        for(int d=c+1;d<=n;d++)
        for(int e=d+1;e<=n;e++)
        for(int f=e+1;f<=n;f++)
        for(int g=f+1;g<=n;g++)
        for(int h=g+1;h<+n;h++)
        for(int i=h+1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        for(int l=j+1;l<=n;l++)
        if(Isprime(a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[i]+a[j]+a[l]))
        ans++;
    }
    if(k==11){
        for(int b=1;b<=n;b++)
        for(int c=b+1;c<=n;c++)
        for(int d=c+1;d<=n;d++)
        for(int e=d+1;e<=n;e++)
        for(int f=e+1;f<=n;f++)
        for(int g=f+1;g<=n;g++)
        for(int h=g+1;h<+n;h++)
        for(int i=h+1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        if(Isprime(sum-(a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[i]+a[j])))
        ans++;
    }
    if(k==12){
        for(int b=1;b<=n;b++)
        for(int c=b+1;c<=n;c++)
        for(int d=c+1;d<=n;d++)
        for(int e=d+1;e<=n;e++)
        for(int f=e+1;f<=n;f++)
        for(int g=f+1;g<=n;g++)
        for(int h=g+1;h<+n;h++)
        for(int i=h+1;i<=n;i++)
        if(Isprime(sum-(a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h]+a[i])))
        ans++;
    }
    if(k==13){
        for(int b=1;b<=n;b++)
        for(int c=b+1;c<=n;c++)
        for(int d=c+1;d<=n;d++)
        for(int e=d+1;e<=n;e++)
        for(int f=e+1;f<=n;f++)
        for(int g=f+1;g<=n;g++)
        for(int h=g+1;h<+n;h++)
        if(Isprime(sum-(a[b]+a[c]+a[d]+a[e]+a[f]+a[g]+a[h])))
        ans++;
    }
    if(k==14){
        for(int b=1;b<=n;b++)
        for(int c=b+1;c<=n;c++)
        for(int d=c+1;d<=n;d++)
        for(int e=d+1;e<=n;e++)
        for(int f=e+1;f<=n;f++)
        for(int g=f+1;g<=n;g++)
        if(Isprime(sum-(a[b]+a[c]+a[d]+a[e]+a[f]+a[g])))
        ans++;
    }
    if(k==15){
        for(int b=1;b<=n;b++)
        for(int c=b+1;c<=n;c++)
        for(int d=c+1;d<=n;d++)
        for(int e=d+1;e<=n;e++)
        for(int f=e+1;f<=n;f++)
        if(Isprime(sum-(a[b]+a[c]+a[d]+a[e]+a[f])))
        ans++;
    }
    if(k==16){
        for(int b=1;b<=n;b++)
            for(int c=b+1;c<=n;c++)
                for(int d =c+1;d<=n;d++)
                for(int e = d+1;e<=n;e++)
                    if(Isprime(sum-(a[b]+a[c]+a[d]+a[e])))
                        ans++;
    }
    if(k==17){
        for(int b=1;b<=n;b++)
            for(int c=b+1;c<=n;c++)
                for(int d =c+1;d<=n;d++)
                    if(Isprime(sum-(a[b]+a[c]+a[d])))
                        ans++;
    }
    if(k==18){
        if(k==2){
        for(int b=1;b<=n;b++){
            for(int c=b+1;c<=n;c++){
                if(Isprime(sum-a[b]-a[c])){
                    ans++;
                }
            }
        }
    }
    }
    if(k==19){
        for(int fuck=1;fuck<=n;fuck++){
            if(Isprime(sum-a[fuck])){
                ans++;
            }
        }
    }
    if(k==20){
        if(Isprime(sum)){
        ans++;}
    }
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    xunhuan(k);
    cout<<ans;
}