Prime Sums

There is a set S = {x[1], x[2], ..., x[n]} and a integer k. Can you tell how many sums of k integers in S which the sums are all primes?

Input

There are several tests, each test contains two lines. The first line consist of an integer n (1 ≤ n ≤ 20) and the integer k (1 ≤ k ≤ n), the second line contains n integers x[1], x[2], ..., x[N] (1 ≤ x[i] ≤ 5000000).

Output

For each test case print in a single line the number of required sums.

Examples