Description

Given $n$ integers $x_1, x_2, \cdots, x_n$, and one integer $k$ ($k<n$). Choose any $k$ integers from the $n$ integers and add them up to obtain a set of sums. For example, when $n=4$, $k=3$, and the four integers are $3, 7, 12, 19$, all combinations and their sums are:

$3+7+12=22$.

$3+7+19=29$.

$7+12+19=38$.

$3+12+19=34$.

Now, you are required to compute how many of these sums are prime numbers.

For example, in the case above, only one sum is prime: $3+7+19=29$.

Input Format

The first line contains two integers $n, k$ separated by a space ($1 \le n \le 20$, $k<n$).

The second line contains $n$ integers $x_1, x_2, \cdots, x_n$ ($1 \le x_i \le 5\times 10^6$).

Output Format

Output a single integer representing the number of ways.

4 3
3 7 12 19

1

Hint

【Source】

NOIP 2002 Junior, Problem 2.

Translated by ChatGPT 5