P3589 [POI 2015 R2] Speed Reading Course

Given $n,a,b,p$, where $n$ and $a$ are coprime. Define a binary string $c_0 c_1 \cdots c_{n-1}$ of length $n$, where $c_i$ equals $0$ if and only if $(ai+b) \bmod n < p$. Given a binary string of length $m$, count how many times the small string appears in the big string.

The first line contains integers $n,a,b,p,m$ ($2\leq n\leq 10^9$, $1\le p,a,b,m

Output a single integer, the number of occurrences of the small string in the big string.

Bold Sample Explanation  ---- Original title: Kurs szybkiego czytania. Translated by ChatGPT 5