18363번 - 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 c₀, c₁, . . . , c_n−1, where c_i = 0 if and only if (ai+b) mod n < p. Finally, Byteasar comes up with another, shorter sequence of m symbols w₀, w₁, . . . , 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 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 w₀, w₁, . . . , 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 ≤ 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 w₀, w₁, . . . , w_m−1 in the sequence c₀, c₁, . . . , 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.