#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
const int mod = 1e5 + 3;

int n, k, cnt, a[N], g[N];
vector<int> fac[N];

int qpow(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = 1ll * res * x % mod;
		}
		x = 1ll * x * x % mod;
		y >>= 1;
	}
	return res;
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j += i) {
			fac[j].emplace_back(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = n; i >= 1; i--) {
		if (a[i]) {
			cnt++;
			for (int j : fac[i]) {
				a[j] ^= 1;
			}
		}
	}
	if (cnt <= k) {
		int ans = cnt;
		for (int i = 1; i <= n; i++) {
			ans = 1ll * ans * i % mod;
		}
		cout << ans << '\n';
		return 0;
	}
	int invn = qpow(n, mod - 2);
	g[n] = 0, g[n - 1] = mod - 1;
	for (int i = n - 2; i >= k; i--) {
		int coe = 1ll * n * qpow(i + 1, mod - 2) % mod;
		g[i] = g[i + 1] - 1ll * (n - (i + 1)) * invn % mod * g[i + 2] % mod;
		if (g[i] < 0) {
			g[i] += mod;
		}
		g[i]--;
		if (g[i] < 0) {
			g[i] += mod;
		}
		g[i] = 1ll * coe * g[i] % mod;
	}
	int x = k - g[k];
	if (x < 0) {
		x += mod;
	}
	int ans = x + g[cnt];
	if (ans >= mod) {
		ans -= mod;
	}
	for (int i = 1; i <= n; i++) {
		ans = 1ll * ans * i % mod;
	}
	cout << ans << '\n';

	return 0;
}