该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

外星球保护计划

时间限制：1s

空间限制：256MB

Description

在太空探索的过程中，小 \(D\) 同学发现了一个神秘的外星文明。他们的星球上有着无数的资源和神秘的生命形式。但是，最近的研究表明，他们的星球上也存在着一些危险。有一些神秘的数字魔盒，如果被不当使用，可能会对整个文明造成威胁。

小 \(D\) 同学的任务就是找出这些数字魔盒，并将它们带回地球进行研究，以确保地球自身的安全。他一共从外星文明带回了 \(N\) 个数字魔盒。现定义一种“方案”如下：从 \(N\) 个数字魔盒中选取 \(K\) 个魔盒，若 \(K\) 个魔盒上的数字之和是质数，那么称这是一个方案。现在地球统领 \(Mr\ W\) 给小 \(D\) 同学下达了死命令，必须要找到所有的方案数，否则就要扣除他一个月的工资。

可怜的小 \(D\) 同学听到了这么恶毒的惩罚后一时乱了阵脚，失去了思考能力。请你帮助小 \(D\) 同学找到所有的方案数，保全他一个月的血汗钱，顺便保护一下宇宙和地球。

Input Format

第一行包含两个整数，魔盒总数 \(N\) 和需要选取的魔盒数 \(K\)

第二行包含 \(N\) 个数字，即 \(N\) 个魔盒上的数字，分别为 \(a_1, a_2, ...,a_N\)

Output Format

一个整数，表示方案数

Data Range

对于\(10\%-30\%\)的数据，\(1 \le N \le10\)

对于\(30\%-60\%\)的数据，\(11 \le N \le 20\)

对于\(70\%-90\%\)的数据，\(21 \le N \le 26\)

对于\(90\%-100\%\)的数据，\(21 \le N \le 26,\left \lceil \frac{N}{2} \right \rceil \le K \le N\)

对于\(100\%\)的数据，\(1 \le K \le N\)

Input Example ：

4 3
3 7 12 19

Output Example ：

1

Note

样例中，我们只有\(3\ ,7 \ ,19\)这一种方案，只有这三个数的和\(29\)为质数