考虑先求出哪些点一定要按，然后 dp。
设 \(f_i\) 为当前还有 \(i\) 个点要按的期望步数。转移就是 \(f_i = \dfrac{i}{n} f_{i-1} + \dfrac{n-i}{n} f_{i+1}\)，初值 \(f_{p} = p,\ p \in [1,k]\)。
这个没办法化简，可能可以高斯消元，但是没写。
考虑换一种 dp 状态。设 \(f_i\) 为当前还有 \(i\) 个点要按 且第一次变为只有 \(i-1\) 个点要按 的期望步数。转移为 \(f_i = \dfrac{i}{n} + \dfrac{n-i}{n} (1 + f_{i+1} + f_i)\)，初值 \(f_n = 1\)。这个显然可以解方程然后递推。
于是就做完了。时间复杂度 \(O(n \ln n)\)。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 100100;
const ll mod = 100003;
int n, m, a[maxn];
ll f[maxn], inv[maxn], fac[maxn];
vector<int> vc[maxn];
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
for (int j = i + i; j <= n; j += i) {
vc[j].pb(i);
}
}
for (int i = n; i; --i) {
for (int x : vc[i]) {
a[x] ^= a[i];
}
}
int k = 0;
for (int i = 1; i <= n; ++i) {
k += a[i];
}
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
if (k <= m) {
printf("%lld\n", fac[n] * k % mod);
return;
}
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
f[n] = 1;
for (int i = n - 1; i; --i) {
f[i] = (n + (n - i) * f[i + 1] % mod) % mod * inv[i] % mod;
}
ll ans = m;
for (int i = k; i > m; --i) {
ans = (ans + f[i]) % mod;
}
ans = ans * fac[n] % mod;
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}