# ZeroJudge - d357: NOIP2002 2.選數
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=d357
###### tags: `ZeroJudge` `數學` `質數` `窮舉`

#include <iostream>
#include <cmath>
using namespace std;
#define SIZE 2500

int primes[SIZE], primeAmount, amount, pick, numbers[20], answer, picked, total;
bool notPrime[SIZE] = { true, true };

void Initialize() {
	for (int i = 2; i < SIZE; ++i) {
		if (!notPrime[i]) {
			primes[primeAmount] = i;
			++primeAmount;
		}
		for (int j = 0; i * primes[j] < SIZE; ++j) {
			notPrime[i * primes[j]] = true;
			if (!(i % primes[j]))
				break;
		}
	}
}

bool IsPrime(int number) {
	int buffer = int(sqrt(number));
	for (int i = 0; primes[i] <= buffer; ++i)
		if (!(number % primes[i])) 
			return false;
	return true;
}

void Picking(int now) {
	if (picked == pick) {
		if (IsPrime(total))
			++answer;
		return;
	}
	for (int i = now; i <= amount - pick + picked; ++i) {
		++picked; total += numbers[i];
		Picking(i + 1);
		--picked; total -= numbers[i];
	}
}

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	cin >> amount >> pick;
	for (int i = 0; i < amount; ++i)
		cin >> numbers[i];
	Initialize(); Picking(0);
	cout << answer << '\n';
}