비트 생성기

어떤 유사난수 비트 생성기는 $0 \le z < m$ 범위의 정수 상태 $z$를 유지한다. 기계를 켜면 상태는 $[0, m-1]$ 범위의 어떤 정수로 설정되며, 이 초기값을 시드(seed)라고 부른다. 비트를 하나 요청할 때마다 생성기는 먼저 상태를 갱신한 뒤 비트를 반환한다. 세 개의 정수 상수 $a$, $c$, $k$를 사용한다.

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

생성기를 $n$번 호출하여 비트열 $b_1, b_2, \ldots, b_n$을 얻었다. 상수들과 이 비트열이 주어질 때, 정확히 이 비트열을 만들어 낼 수 있는 시드가 몇 개인지 구하여라.

첫째 줄에 다섯 정수 $a$, $c$, $k$, $m$, $n$이 주어진다. ($0 \le a, c < m$, $1 \le k < m$, $2 \le m \le 10^6$, $1 \le n \le 10^5$)

둘째 줄에 0 또는 1로 이루어진 길이 $n$의 문자열이 주어진다. $i$번째 문자가 비트 $b_i$이다.

$0 \le z < m$ 범위의 정수 중, 초기 상태(시드)로서 정확히 주어진 비트열을 생성할 수 있는 값의 개수를 정수 하나로 출력한다.