题目描述

给定 $n,a,b,p$，其中 $n,a$ 互质。

定义一个长度为 $n$ 的 01 串 $c_0c_1\cdots c_{n-1}$，其中 $c_i$ 等于 0 当且仅当 $(ai+b) \bmod n < p$。

给定一个长为 $m$ 的小 01 串，求出小串在大串中出现了几次。

输入格式

第一行包含整数 $n,a,b,p,m$（$2\leq n\leq 10^9$，$1\le p,a,b,m<n$，$1\le m\le 10^6$）。保证 $n$ 和 $a$ 互质。

第二行一个长度为 $m$ 的 01 串。

输出格式

一个整数，表示小串在大串中出现了几次。

9 5 6 4 3
101

3

提示

【样例解释】

原题名称：Kurs szybkiego czytania