[POI2015] KUR

题目描述

给定 $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 串。

输出格式


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

输入输出样例

输入样例 #1

9 5 6 4 3
101

输出样例 #1

3

说明

**【样例解释】** ![](https://cdn.luogu.com.cn/upload/image_hosting/qd6imu53.png) ---- 原题名称:Kurs szybkiego czytania