#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <stack>
#include <vector>
using namespace std;

int n, k;
vector<int> a;

bool isPrime(int number)
{
    for (int i = 2; i < sqrt(number); ++i)
    {
        if (number % i == 0)
        {
            return false;
        }
    }
    return true;
}

int caculateHelper(vector<int> &arr, int index, int count, int oddNumber)
{
    if (count == k)
    {
        //如果奇数的数量位偶数，和一定为偶数，不用判断
        if (oddNumber % 2 == 0)
        {
            return 0;
        }
        int temp = 0;
        for (int i = 0; i < arr.size(); ++i)
        {
            temp += arr[i];
        }
        return isPrime(temp) ? 1 : 0;
    }
    //剪枝
    if (count + n - index < k)
    {
        return 0;
    }
    int ans = 0;

    arr.push_back(a[index]);
    ans += caculateHelper(arr, index + 1, count + 1, oddNumber + (a[index] % 2 == 1 ? 1 : 0));
    arr.pop_back();
    ans += caculateHelper(arr, index + 1, count, oddNumber);

    return ans;
}

int caculate()
{
    vector<int> arr;
    return caculateHelper(arr, 0, 0, 0);
}

int main()
{
    cin >> n >> k;

    for (int i = 0; i < n; ++i)
    {
        int temp;
        cin >> temp;
        a.push_back(temp);
    }
    cout << caculate();
}