Zeit und Raum trennen dich und mich.

B is playing a game consisting of $n$ lights and $n$ switches. You are given the initial state of these $n$ lights, indexed from $1$ to $n$.

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

When the $i$-th switch is operated, the state of all lights whose index is a divisor of $i$ (including $1$ and $i$) is toggled (i.e., on becomes off, and off becomes on).

B finds this game difficult, so he comes up with the following strategy: at each step, he chooses a switch to operate uniformly at random, until all lights are off.

Since this strategy requires many operations, B thinks of an optimization. If the current state can be solved by operating at most $k$ switches, he stops acting randomly and instead chooses the optimal sequence of operations (which is guaranteed to be at most $k$ steps) to turn all lights off.

B wants to know the expected number of operations following this strategy (i.e., acting randomly until the state can be solved in at most $k$ steps, then using the optimal sequence).

This expectation might be very large, but B discovers that the expectation multiplied by $n!$ is always an integer. Therefore, he only needs to know the result of this integer modulo $100003$.

Input

The first line contains two integers $n$ and $k$.

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

Output

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

Subtasks

• For $0\%$ of the test cases, the input is identical to the sample.
• For another $30\%$ of the test cases, $n \le 10$.
• For another $20\%$ of the test cases, $n \le 100$.
• For another $30\%$ of the test cases, $n \le 1000$.
• For $100\%$ of the test cases, $1 \le n \le 100000$, $0 \le k \le n$.
• For each of the above parts, half of the data satisfies $k = n$.

Examples

Input 1

4 0
0 0 1 1

Output 1

512

Input 2

5 0
1 0 1 1 1

Output 2

5120