Speed reading course

Byteasar has enrolled in a speed reading course, which has taught him many perception improving exercises. 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 four integers n, a, b, and p such that n and a are coprime, and the computer generates a sequence c0, c1, . . . , cn−1, where ci = 0 if and only if (ai+b) mod n < p. Finally, Byteasar comes up with another, shorter sequence of m symbols w0, w1, . . . , wm−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 your help in writing a program that will verify if indeed he found all the occurrences.

The first line of the standard input contains five integers, n, a, b, p, and m (2 ≤ n ≤ 1 000 000 000, 1 ≤ p, a, b, m < n, 1 ≤ m ≤ 1 000 000), separated by single spaces. The numbers a and n are coprime. In the second line, there is a word w0, w1, . . . , wm−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 ≤ 1000 holds;
• in other tests worth 8% of the total score, n ≤ 1 000 000 holds;
• in yet other tests worth 66% of the total score, m ≤ 1000 holds.

The first and only line of the standard output should contain an integer equal to the number of occurrences of the sequence w0, w1, . . . , wm−1 in the sequence c0, c1, . . . , cn−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.