选数

题目描述

Y 同学获得了一个长度为 $N$ 的正整数序列 $X = (X_1, X_2, \dots, X_N)$，以及一个目标选择数量 $K$。

Y 同学需要从这 $N$ 个正整数中任意挑选出恰好 $K$ 个元素构成一个集合。设选出的下标集合为 $S$（满足 $S \subseteq \{1, 2, \dots, N\}$ 且 $|S| = K$），他会计算这些被选中元素的总和 $\sum_{i \in S} X_i$。

请你编写程序，帮助 Y 同学求出，在所有可能的 $\binom{N}{K}$ 种选择方案中，有多少种方案使得选出的 $K$ 个元素的和恰好为一个素数（质数）。

输入格式

第一行包含两个整数 $N$ 和 $K$，相邻两个整数之间由一个空格隔开，分别表示序列的长度和需要挑选的元素个数。

第二行包含 $N$ 个整数 $X_1, X_2, \dots, X_N$，相邻两个整数之间由一个空格隔开，表示给定的正整数序列。

输出格式

输出一行一个整数，表示和为素数的选择方案总数。

样例

样例输入 #1

4 3
3 7 12 19

样例输出 #1

1

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 20$，$1 \le K < N$，$1 \le X_i \le 5 \times 10^6$。