#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#include<cstdlib>

#include<vector>

#define maxn 100020

#define mod 100003

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

vector<long long>s[maxn];

long long inv[maxn];

long long q[maxn];

long long f[maxn];

int main(){

    long long n=read(),m=read();

    inv[]=;

    for(long long i=;i<=n;++i)    inv[i]=(-mod/i*inv[mod%i]%mod+mod)%mod;

    for(long long i=;i<=n;++i)    q[i]=read();

    for(long long i=;i<=n;++i)

        for(long long j=i;j<=n;j+=i)    s[j].push_back(i);

    long long last=;

    for(long long i=n;i>=;--i){

        if(q[i]==)    continue;

        for(long long j=;j<s[i].size();++j)    q[s[i][j]]^=;

        last++;

    }

    f[n]=;

    for(long long i=n-;i>m;--i)    f[i]=(n*inv[i]%mod+((n-i)*f[i+]%mod)*inv[i]%mod)%mod;

    for(long long i=;i<=m;++i)    f[i]=;

    long long ans=;

    for(long long i=;i<=last;++i)    ans=(ans+f[i])%mod;

    for(long long i=;i<=n;++i)    ans=(ans*i)%mod;

    printf("%d\n",ans);

    return ;

}