#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=3e5+10;
const int maxm=1e6+10;
const ll mod=1e5+3;
const ll base=1e8;
const ull base1=233;
const ull base2=19260817;
const int maxxn=0x7fffffff;
const int minxn=-0x7fffffff;
const db inf=1e13;
const db eps=1e-9;
inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}
int n,k;
int a[maxn];
int cnt;
ll dp[maxn],ans;
inline ll q_pow(ll x,int p){
	ll ans=1;
	while(p){
		if(p&1){
			ans=ans*x%mod;
		}
		x=x*x%mod;
		p>>=1;
	}
	return ans;
}
int main(){
	n=read(),k=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=n;i>=1;i--){
		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;
				}
				
			}
		}
	}
	dp[n+1]=0;
	for(int i=n;i>=1;i--){
		dp[i]=(n+dp[i+1]*(n-i)%mod)%mod;
		dp[i]=dp[i]*q_pow(i,mod-2)%mod;
	}
	if(cnt<=k) ans=cnt;
	else{
		for(int i=cnt;i>k;i--){
			ans=(ans+dp[i])%mod;
		}
		ans=(ans+k)%mod;
	}
	for(int i=1;i<=n;i++){
		ans=(ans*i)%mod;
	}
	printf("%lld\n",ans);
	return 0;
}