题目描述

给定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