시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 64 MB 0 0 0 0.000%

## 문제

Byteasar likes to play with his random (well, actually pseudorandom) bits generator, which he has found on his computer. This generator works in a very simple way. The moment the computer is turned on, an integer in the range between 0 and m − 1 is chosen automagically. This integer is called the seed of the generator; we will use variable z to represent it. Then, in order to generate a random bit, the following function is called. It computes a new value of the seed which is then used to generate a single bit:

z := ⌊(z · a + )=k⌋ mod m
if z < ⌊m=2⌋ then
return 0
else
return 1

The numbers a, c, k are some constants. Byteasar has called this function n times and has thus obtained a sequence of bits b1, b2, ..., bn. Now he is wondering what is the number of different possible values of the initial seed.

## 입력

The first line of the input contains five integers a, c, k, m and n (0 ≤ a, c < m, 1 ≤ k < m, 2 ≤ m ≤ 1 000 000, 1 ≤ n ≤ 100 000). The second line contains an n-character string consisting of digits 0 and 1; the i-th digit of the string represents the bit bi.

## 출력

You should output one integer representing the number of integers from the range between 0 and m− 1 which could have been the initial seed of the generator.

## 예제 입력 1

3 6 2 9 2
10


## 예제 출력 1

4


## 힌트

Explanation of the example: The initial seed of the generator could have been equal to 1, 2, 7 or 8.