#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// [1] 全局变量定义
int n, k;             // n-输入的数字总数，k-需要选取的数字个数
vector<int> a;        // 存储输入的n个数字
int ans = 0;          // 统计和为素数的k数组合数量

// [4] 素数判断函数：用long long避免求和溢出，试除法实现
bool is_prime(long long x) {
    // [4.1] 小于等于1的数不是素数
    if (x <= 1) return false;
    // [4.2] 2是唯一的偶素数
    if (x == 2) return true;
    // [4.3] 大于2的偶数直接排除，非素数
    if (x % 2 == 0) return false;
    // [4.4] 试除法检查奇数：仅需验证3到sqrt(x)的奇数
    for (long long i = 3; i <= sqrt(x); i += 2) {
        if (x % i == 0) return false; // 能被整除则非素数
    }
    // [4.5] 所有验证通过，是素数
    return true;
}

// [3] DFS递归函数：生成不重复的k数组合并计算和
// 参数：start-遍历起始索引（防重复），cnt-已选数字数量，sum-当前组合的和
void dfs(int start, int cnt, long long sum) {
    // [3.1] 递归终止条件：已选够k个数字
    if (cnt == k) {
        // [3.2] 若当前组合和为素数，符合条件的组合数+1
        if (is_prime(sum)) {
            ans++;
        }
        return;
    }
    // [3.3] 从start开始遍历，保证索引递增，避免生成重复组合
    for (int i = start; i < n; i++) {
        // [3.4] 递归下一层：起始索引+1，已选数+1，和累加当前数字
        dfs(i + 1, cnt + 1, sum + a[i]);
    }
}

// [2] 主函数：处理输入、启动DFS、输出结果
int main() {
    // [2.1] 输入数字总数n和需选取的个数k
    cin >> n >> k;
    // [2.2] 初始化数组并读取n个输入数字
    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i]; // 读取第i个数字存入数组a
    }
    // [2.3] 启动DFS：初始从索引0开始，已选0个，和为0
    dfs(0, 0, 0);
    // [2.4] 输出最终符合条件的组合数量
    cout << ans << endl;
    return 0;
}