质数选数

题目描述

给定 n 个正整数。请从中选择恰好 k 个位置，使这些位置上的数之和为质数，并统计不同选择方案的数量。

如果两个方案选择的位置集合不同，就认为它们是不同方案。即使不同位置上的数值相同，也仍然按不同元素处理。

输入格式

第一行输入两个整数 n k。

第二行输入 n 个正整数 a1,a2,...,an。

输出格式

输出一个整数，表示合法选择方案数。

样例输入

4 3
3 7 12 19

样例输出

1

样例说明

只有选择 3、7、19 时，和为质数 29。

数据范围

对于全部数据：

• 1 <= k <= n <= 20；
• 1 <= ai <= 5000。