#include <cstdio>
#define int long long
const int M = 100005;
const int MOD = 100003;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,k,cnt,ans,a[M],f[M];
int qkpow(int a,int b)
{
	int r=1;
	while(b>0)
	{
		if(b&1) r=r*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return r;
}
signed main()
{
	n=read();k=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=n;i>=1;i--)
	{
		f[i]=(n+(n-i)*f[i+1]%MOD)*qkpow(i,MOD-2)%MOD;
		if(a[i])
		{
			cnt++;
			for(int j=1;j*j<=i;j++)
				if(i%j==0)
				{
					a[j]^=1;
					if(j*j!=i) a[i/j]^=1;
				}
		}
	}
	if(cnt<=k) ans=cnt;
	else
	{
		for(int i=cnt;i>k;i--) ans=(ans+f[i])%MOD;
		ans=(ans+k)%MOD;
	}
	for(int i=1;i<=n;i++) ans=ans*i%MOD;
	printf("%lld\n",ans);
}