选数求和为质数的方案数问题

题目描述

梦梦给出了$n$个整数$a_1,a_2,\cdots,a_n$，熊熊从中选出$k$个数（每个数字至多选一次），使得选出的这$k$个数的和恰好为质数，现在需要计算满足这样条件的选数方案一共有多少种。

输入格式

1. 第一行包含两个用空格隔开的整数$n$和$k$，分别表示整数的总个数以及要选出的数的个数，其中$1\leq k\leq n\leq 20$。
2. 第二行包含$n$个整数，分别为$a_1,a_2,\cdots,a_n$，每个整数满足$1\leq a_i\leq 5*10^6$

输出格式

输出一个整数，表示选出$k$个数其和为质数的选数方案的种类数。

样例

样例输入

4 3
1 2 3 4

样例输出

1

样例解释

选择$1$、$2$、$4$这三个数，它们的和为$1 + 2 + 4 = 7$，恰好为质数，所以满足条件的选数方案有$1$种。

数据范围与提示

1. 对于$30\%$的数据，$1\leq k\leq 1$。
2. 对于$60\%$的数据，$1\leq k\leq 2$。
3. 对于$100\%$的数据，$1\leq n\leq 20$，$1\leq k\leq n$，$1\leq a_i\leq 5*10^6$。