9260 - 素数种类

通过次数

23

提交次数

50

时间限制 : 1 秒
内存限制 : 128 MB

已知n个整数x_1,x_2,......x_n以及1个整数k(k<n)。从n个整数中任选k个整数相加,可分别得到一系列的和。现在,要求你计算出和为素数的共有多少种。

输入

第一行两个空格隔开的整数n,k(1 <n ≤ 20,k<n)。 第二行n个整数,分别为x_1,x_2,......x_n(1 ≤ x_i≤5*10^6)。

输出

输出一个整数,表示种类数。

样例

输入

4 3
3 7 12 19

输出

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=29,故输出1。

来源

云南编程挑战赛