Separation of Time and Space

B is playing a game with n lights and n switches. The lights are numbered from \(1\) to \(n\) and each light can be either on or off. A light is on if its state is \(1\) and off if its state is \(0\). The initial configuration of the lights is given.

For \(i=1,2,\dots,n\), the \(i\)th switch toggles the state of all lights whose indices are divisors of \(i\) (i.e. every light \(j\) such that \(j\mid i\), including \(j=1\) and \(j=i\)). Toggling means that an on light becomes off and an off light becomes on. The goal of the game is to switch all lights off.

Because the game is difficult, B has devised a two‐phase strategy. In the first phase, at each step he randomly chooses one switch to operate (each of the \(n\) switches is equally likely) until the current configuration \(s\) becomes "close" – namely, when it is possible to switch off all lights in at most \(k\) moves with an optimal (minimum‐move) strategy. When such a configuration is reached (i.e. when the minimum number \(g(s)\) of moves required satisfies \(g(s)\le k\)), he stops the random moves and then in the second phase he applies the optimal sequence that uses exactly \(g(s)\) moves.

B is interested in the expected total number of operations (random moves plus the final optimal moves) performed under this strategy. It can be shown that if you multiply the expected number of moves by \(n!\) (\(n\) factorial) the result is always an integer. Your task is to compute that integer modulo 100003.

Notes:

• When operating a switch \(i\), the new state is \(s \oplus v_i\) where \(v_i\) is a binary vector (over \(\mathbb{F}_2\)) whose \(j\)th component is \(1\) if \(j\mid i\) and \(0\) otherwise, and \(\oplus\) denotes bitwise XOR.
• The minimum number of moves \(g(s)\) for a configuration \(s\) is the minimum number of switches (each used at most once, since toggling twice cancels out) needed to make all lights off.

inputFormat

The first line contains two integers \(n\) and \(k\) \((1 \le n \le \text{small, e.g. } 10)\). The second line is a binary string of length \(n\) representing the initial states of the lights; the \(i\)th character is \(1\) if light \(i\) is on and \(0\) otherwise.

outputFormat

Output one integer: the value of (expected number of operations \(\times n!\)) modulo 100003.

sample

2 1
10

2