# include <bits/stdc++.h>
using namespace std;
const int mod=100003;
typedef long long ll;
int a[100010],f[100010][2];
ll inv[100010];
ll power(ll a,int b)
{
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1) ans=ans*a%mod;
	return ans;
}
int main()
{
	int n,k,c=0,fac=1;
	cin>>n>>k;
	inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod,fac=(ll)fac*i%mod;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=n;i>=1;i--)
		for(int j=2*i;j<=n;j+=i)
			a[i]^=a[j];
	for(int i=1;i<=n;i++) c+=a[i];
	if(c<=k) return cout<<(ll)c*fac%mod<<endl,0;
	f[n][1]=f[n-1][1]=1;f[n-1][0]=mod-1;
	for(int i=n-1;i>k;i--)
	{
		f[i-1][0]=((ll)n*f[i][0]+(ll)(mod-n+i)*f[i+1][0]+mod-n)%mod*inv[i]%mod;
		f[i-1][1]=((ll)n*f[i][1]+(ll)(mod-n+i)*f[i+1][1])%mod*inv[i]%mod;
	}
	ll v=(k-f[k][0]+mod)*power(f[k][1],mod-2)%mod;
	cout<<(v*f[c][1]+f[c][0])%mod*fac%mod<<endl;
	return 0;
}