题目描述

给定 $n$ 个正整数 $a_1, a_2, \cdots, a_n$ 和一个正整数 $k$（$k \lt n$）。你需要从这 $n$ 个数中恰好选出 $k$ 个，将它们求和。问一共有多少种选法，使得选出的 $k$ 个数之和恰好是一个质数。

例如 $n=4$，$k=3$，四个数分别为 $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$。

输入格式

第一行包含两个正整数 $n$ 和 $k$，用空格分隔（$1 \le n \le 20$，$k \lt n$）。

第二行包含 $n$ 个正整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le 5 \times 10^6$）。

输出格式

输出一个整数，表示和为质数的选法总数。

样例

4 3
3 7 12 19

1

提示

数据范围：$1 \le n \le 20$，$k \lt n$，$1 \le a_i \le 5 \times 10^6$。

质数定义：大于 $1$ 的正整数，除了 $1$ 和它自身外没有其他正因数。