#include<stdio.h>
#include<bits/stdc++.h>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;

const int N=1e5+5,mod=100003;
int n,k,cnt,ans;
bool x[N];
int f[N];

inline int fpow(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;
}

inline int inv(int x)
{
	return fpow(x,mod-2);
}

int main(void)
{
	scanf("%d%d",&n,&k);
	for(register int i=1;i<=n;++i)
		scanf("%d",x+i);
	for(register int i=n;i;--i)
		if(x[i])
		{
			++cnt;
			for(register int j=1;j*j<=i;++j)
				if(i%j==0)
				{
					x[j]^=1;
					if(j*j!=i) x[i/j]^=1;
				}
		}
	for(register int i=n;i;--i)
		f[i]=(n+1ll*(n-i)*f[i+1])%mod*inv(i)%mod;
	ans=min(cnt,k);
	for(register int i=cnt;i>=k+1;--i)
		ans=(ans+f[i])%mod;
	for(register int i=1;i<=n;++i)
		ans=1ll*ans*i%mod;
	printf("%d\n",ans);
	return 0;
}