Description

Zeit und Raum trennen dich und mich. Time and space separate you and me.

B-kun is playing a game with $n$ lights and $n$ switches. The $n$ lights have initial states and are indexed by the positive integers from $1$ to $n$.

Each light has two states, on and off. We use $1$ to indicate the light is on and $0$ to indicate it is off. The goal of the game is to turn all lights off.

When operating the $i$-th switch, the states of all lights whose indices are divisors of $i$ (including $1$ and $i$) are toggled, i.e., on becomes off, and off becomes on.

B-kun finds this game difficult, so he considers the following strategy: at each step, uniformly at random choose one switch to operate, until all lights are off.

This strategy may require many operations, so B-kun thinks of the following optimization. If, in the current state, it is possible to turn all lights off by pressing at most $k$ switches, then he will stop acting randomly and directly choose a method with the minimum number of operations (which is clearly at most $k$) to press those switches.

B-kun wants to know the expected number of operations under this strategy (that is, act randomly first, and finally, if at most $k$ steps suffice, use the method with the minimum number of operations).

This expectation may be large, but B-kun observes that the expectation multiplied by $n!$ is always an integer, so he only needs this integer modulo $100003$.

Input Format

The first line contains two integers $n, k$.
The next line contains $n$ integers, each being $0$ or $1$, where the $i$-th integer indicates the initial state of the $i$-th light.

Output Format

Output one line: the expectation of the number of operations multiplied by $n!$, modulo $100003$.

4 0
0 0 1 1

512

5 0
1 0 1 1 1

5120

Hint

For $0\%$ of the testdata, the input is identical to the sample.
For an additional $30\%$ of the testdata, $n \leq 10$.
For an additional $20\%$ of the testdata, $n \leq 100$.
For an additional $30\%$ of the testdata, $n \leq 1000$.
For $100\%$ of the testdata, $1 \leq n \leq 100000, 0 \leq k \leq n$.
For each of the above parts of the testdata, half of the testdata satisfies $k = n$.

Translated by ChatGPT 5