题目描述

某算法竞赛训练中，给定 m 个正整数 a₁, a₂, ⋯, aₘ，以及 1 个整数 t（t < m）。要求从这 m 个整数中无重复地选取 t 个整数进行求和，得到若干个不同的和值。 请统计这些和值中，属于「素数」的数量。 （素数定义：大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数）。

输入格式

第一行输入两个空格分隔的整数 m 和 t（1 ≤ m ≤ 20，t < m）；第二行输入 m 个整数，依次为 a₁, a₂, ⋯, aₘ（1 ≤ aᵢ ≤ 5×10⁶）。

输出格式

输出一个整数，表示选取 t 个数求和后，和为素数的组合数量。

样例

4 3
3 7 12 19

1

样例解释

当 m=4，t=3，4 个整数为 3、7、12、19 时，所有选 3 个数求和的组合及结果为： 3+7+12 = 22（非素数） 3+7+19 = 29（素数） 7+12+19 = 38（非素数） 3+12+19 = 34（非素数） 最终符合条件的素数和共有 1 种。

说明

组合顺序不影响结果（如「3+7+19」和「7+3+19」视为同一组合）。