Speed Reading Course

Byteasar has enrolled in a speed reading course, which taught him many exercises for improving perception. His favorite one is finding a pattern in a sequence of symbols. For this exercise, Byteasar has a computer generate a very long sequence of zeros and ones as follows. He chooses integers $n$, $a$, $b$, and $p$ such that $n$ and $a$ are coprime, and the computer generates a sequence $c_0, c_1, \dots, c_{n-1}$, where $c_i = 0$ if and only if $(ai+b) \bmod n < p$. Finally, Byteasar comes up with another, shorter sequence of $m$ symbols $w_0, w_1, \dots, w_{m-1}$. Set up with these, his task is to find all occurrences of the shorter sequence in the one generated by the computer as quickly as possible. He has asked for your help in writing a program that will verify whether he indeed found all the occurrences.

The first line of the standard input contains five integers, $n$, $a$, $b$, $p$, and $m$ ($2 \le n \le 1\,000\,000\,000$, $1 \le p, a, b, m < n$, $1 \le m \le 1\,000\,000$), separated by single spaces. The numbers $a$ and $n$ are coprime. In the second line, there is a word $w_0, w_1, \dots, w_{m-1}$, consisting of $m$ symbols, each either 0 or 1. The following mutually exclusive classes form a subset of all the test inputs:

• in tests worth 8% of the total score, $n \le 1000$ holds;
• in other tests worth 8% of the total score, $n \le 1\,000\,000$ holds;
• in yet other tests worth 66% of the total score, $m \le 1000$ holds.

The first and only line of the standard output should contain an integer equal to the number of occurrences of the sequence $w_0, w_1, \dots, w_{m-1}$ in the sequence $c_0, c_1, \dots, c_{n-1}$.

For $n = 9$, $a = 5$, $b = 6$, and $p = 4$, the computer generates the sequence as follows:

The sequence 101 occurs thrice in the sequence 101011010.