记录编号	577968	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HEOI 2017] 分手是祝愿	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.122 s
提交时间	2022-12-20 16:34:26	内存使用	1.87 MiB

#include <bits/stdc++.h>
#define pb emplace_back
using i64 = long long;

const i64 mod = 1e5 + 3;
const int maxn = 1e5 + 5;
int n,k,a[maxn];
std::vector<int> G[maxn];
i64 b[maxn],f[maxn];

i64 power(i64 x,i64 y) {
	i64 ans = 1;
	for(;y;y >>= 1) {
		if(y & 1)(ans *= x) %= mod;
		(x *= x) %= mod;
	}
	return ans;
}

int main() {
	freopen("trennen.in","r",stdin);
	freopen("trennen.out","w",stdout);
	scanf("%d %d",&n,&k);
	for(int i = 1;i <= n;++ i)
		for(int j = i;j <= n;j += i)
			G[j].pb(i);
	for(int i = 1;i <= n;++ i)
		scanf("%d",&a[i]);
	i64 tot = 1;
	int cnt = 0;
	for(int i = n;i;-- i) {
		tot = 1ll * tot * i % mod;
		if(!a[i])continue ;
		++ cnt;
		for(auto& k : G[i])
			a[k] ^= true;
	}
	b[n] = 1;
	if(k >= cnt) {
		printf("%lld\n",cnt * tot % mod);
		return 0;
	}
	for(int i = n - 1;i;-- i)
		b[i] = (1ll * (n - i) * b[i + 1] % mod + n) % mod * power(i , mod - 2) % mod;
	f[k] = k;
	for(int i = k + 1;i <= n;++ i)
		f[i] = (f[i - 1] + b[i]) % mod;
	printf("%lld\n",f[cnt] * tot % mod);
	return 0;
}