[POI2015]Kurs szybkiego czytania

时间限制:10s      空间限制:128MB

题目描述

给定n,a,b,p,其中n,a互质。定义一个长度为n的01串c[0..n-1],其中c[i]==0当且仅当(ai+b) mod n < p。
给定一个长为m的小01串,求出小串在大串中出现了几次。


输入格式

第一行包含整数n,a,b,p,m(2<=n<=10^9,1<=p,a,b,m<n,1<=m<=10^6)。n和a互质。
第二行一个长度为m的01串。


输出格式

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


样例输入

9 5 6 4 3
101

样例输出

3

提示


题目来源

鸣谢Claris