Description

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.

Input Format

The first line contains integers $n,a,b,p,m$ ($2\leq n\leq 10^9$, $1\le p,a,b,m<n$, $1\le m\le 10^6$). It is guaranteed that $n$ and $a$ are coprime.

The second line contains a binary string of length $m$.

Output Format

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

9 5 6 4 3
101

3

Hint

Bold Sample Explanation

Original title: Kurs szybkiego czytania.

Translated by ChatGPT 5