B. 选素数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

已知 n 个整数 x_1,x_2,...,x_n ,以及一个整数 k(k<n)。

从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。

现在,要求你计算出和为素数共有多少种。

输入格式

第一行: n,k(1≤n≤20, k<n)

第二行: x_1,x_2,...,x_n(1≤x_i≤5000000)

输出格式

输出格式为:一个整数(满足条件的方案数)。

样例

#输入1

4 3
3 7 12 19

#输出1

1

说明:当 n=4,k=3,4个整数分别为 3,7,12,19 时,可得全部的组合有四种,它们的和分别为:

3+7+12=22, 3+7+19=29, 7+12+19=38, 3+12+19=34.

因此,和为素数的只有一种:3+7+19=293+7+19=29。