Substring Occurrence in a Generated Binary String

Given four integers \(n, a, b, p\) where \(n\) and \(a\) are coprime. Define a binary string \(c_0c_1\cdots c_{n-1}\) of length \(n\) such that \(c_i = 0\) if and only if \((ai+b) \bmod n < p\), and \(c_i = 1\) otherwise.

You are also given a smaller binary string \(s\) (of length \(m\)). Your task is to determine how many times \(s\) occurs in the generated binary string \(c\). Note that occurrences may overlap.

inputFormat

The first line contains four space-separated integers: \(n\), \(a\), \(b\), and \(p\) (with \(\gcd(n,a)=1\)).

The second line contains a binary string \(s\) representing the pattern to search for in \(c\).

outputFormat

Output a single integer representing the number of occurrences of the pattern \(s\) in the large binary string \(c\).

sample

7 3 1 4
01

1