You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Given $n$ integers $x_1$, $x_2$, ..., $x_n$, and an integer $k$ ($k < n$). From these $n$ integers, choose any $k$ integers and add them together to get a series of sums. For example, when $n=4$, $k=3$, and the $4$ integers are $3$, $7$, $12$, $19$, all possible combinations and their sums are:
$3+7+12=22$
$3+7+19=29$
$7+12+19=38$
$3+12+19=34$
Now, you need to calculate how many of these sums are prime numbers.
In the example above, only one sum is prime: $3+7+19=29$.

Input Format

The first line contains $n$ and $k$ ($1 ≤ n ≤ 20$, $k < n$).
The second line contains $n$ numbers:
$x_1$ $x_2$ ... $x_n$ ($1 ≤ x_i ≤ 5000000$), separated by spaces.

Output Format

A single integer representing the number of combinations that sum to a prime number.

Sample

4 3
3 7 12 19

1