Prime Sum Combinations

Given an integer sequence \(x_1, x_2, \cdots, x_n\) and an integer \(k\) (with \(k < n\)), select any \(k\) integers from the sequence and compute their sum. Your task is to count the number of combinations whose sum is a prime number.

For example, when \(n = 4\), \(k = 3\), and the sequence is \(3, 7, 12, 19\), the possible combinations and their sums are:

• \(3 + 7 + 12 = 22\)
• \(3 + 7 + 19 = 29\)
• \(7 + 12 + 19 = 38\)
• \(3 + 12 + 19 = 34\)

In this example, only \(29\) is a prime number, so the answer is 1.

inputFormat

The first line contains two integers \(n\) and \(k\) separated by a space, where \(k < n\). The second line contains \(n\) integers separated by spaces, representing the sequence \(x_1, x_2, \cdots, x_n\).

outputFormat

Output a single integer representing the number of combinations (of \(k\) integers) whose sum is a prime number.

sample

4 3
3 7 12 19

1