题目描述

已知 $n$ 个整数 $x_1, x_2, \cdots, x_n$，以及一个整数 $k$（$1 \leq k < n$）。
从 $n$ 个整数中任选 $k$ 个数相加，可以得到若干个不同的和。
现在，要求你计算其中有多少种和是素数。

例如当 $n = 4$，$k = 3$，四个整数为 $3, 7, 12, 19$，所有的组合及其和如下：

• $3 + 7 + 12 = 22$
• $3 + 7 + 19 = 29$
• $3 + 12 + 19 = 34$
• $7 + 12 + 19 = 38$

其中只有 $29$ 是素数，因此输出为 $1$。

输入格式

第一行包含两个整数 $n, k$（$1 \leq n \leq 20$，$1 \leq k < n$）。

第二行包含 $n$ 个正整数，表示 $x_1, x_2, \cdots, x_n$（$1 \leq x_i \leq 5 \times 10^6$）。

输出格式

输出一个整数，表示种类数。

样例输入

4 3
3 7 12 19

样例输出

1