Problem Description

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

B-Jun is playing a game with $n$ lights and $n$ switches, where each light has an initial state, indexed from $1$ to $n$.

Each light has two states: on and off. We use $1$ to represent a light that is on and $0$ to represent a light that is off. The goal of the game is to turn off all the lights.

When the $i$-th switch is operated, the state of all lights whose indices are divisors of $i$ (including $1$ and $i$) will be changed, i.e., from on to off, or from off to on.

B-Jun finds the game difficult, so he comes up with a strategy: he will randomly operate a switch with equal probability until all lights are off.

This strategy requires many operations. B-Jun thinks of an optimization: if the current state can be turned off by operating no more than $k$ switches, he will no longer randomize but directly choose the minimum number of operations (which is obviously no more than $k$ steps) to operate these switches.

B-Jun wants to know the expected number of operations according to this strategy (starting with random operations, then using the minimum number of operations if it is no more than $k$ steps).

This expectation might be very large, but B-Jun realizes that the expectation multiplied by $n$ factorial is an integer, so he only needs to know the result of this integer modulo $100003$.

Input Format

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

Output Format

Output a single line, which is the expected number of operations multiplied by $n$ factorial modulo $100003$.

Sample Input and Output

Sample Input #1

4 0
0 0 1 1

Sample Output #1

512

Sample Input #2

5 0
1 0 1 1 1

Sample Output #2

5120

Notes/Hints

For $0\%$ of the test points, the input is exactly the same as the sample;
For another $30\%$ of the test points, $n \leq 10$;
For another $20\%$ of the test points, $n \leq 100$;
For another $30\%$ of the test points, $n \leq 1000$;
For $100\%$ of the test points, $1 \leq n \leq 100000, 0 \leq k \leq n$;
For each of these test point sections, half of the data satisfies $k = n$.

见题面 Input 部分

见题面 Output 部分