Bits Generator

A pseudorandom bit generator keeps an integer state $z$ with $0 \le z < m$. When the machine is switched on, the state is set to some integer in $[0, m-1]$; this starting value is called the seed. Each time a bit is requested, the generator first updates its state and then returns a bit, using three fixed integer constants $a$, $c$, and $k$:

z := floor((z * a + c) / k) mod m
if z < floor(m / 2):
    return 0
else:
    return 1

The generator was queried $n$ times, producing a bit sequence $b_1, b_2, \ldots, b_n$. Given the constants and this sequence, determine how many of the possible seeds could have produced exactly this sequence.

The first line contains five integers $a$, $c$, $k$, $m$, and $n$, with $0 \le a, c < m$, $1 \le k < m$, $2 \le m \le 10^6$, and $1 \le n \le 10^5$.

The second line contains a string of exactly $n$ characters, each 0 or 1; the $i$-th character is the bit $b_i$.

Print a single integer: the number of seeds $z$ with $0 \le z < m$ that could have been the initial state, i.e. that produce exactly the given bit sequence.