Alice 和 Bob 又又又又在做游戏了！但他们已经厌倦了博弈游戏，他们决定尝试一些别的。
现在 Alice 给了 Bob 一个 01 串 T，同时给了他四个整数 $n$，$a$，$b$，$p$。Alice 用这四个整数构造了一个 01 串 $S[0...n - 1]$，其中 $S_i = 0$ 当且仅当
$$ (a_i + b) \mod n < p $$
现在 Alice 需要 Bob 求出字符串 T 在 S 中出现了多少次。
Bob 并不会解决这个问题。为了不成为时代的眼泪，他找到了小 X 同学。但刚刚被白嫖的小 X 同学很不爽，于是他把这个问题交给了你。
以下是将您提供的内容整理为 Markdown 格式，并包含数学公式的版本：
输入格式
第一行包括整数 $n$，$a$，$b$，$p$，$m$。
第二行一个长度为 $m$ 的 01 序列，表示字符串 $T$。
输出格式
一个整数，表示 $T$ 在 $S$ 中出现的次数。
样例 1
输入
9 5 6 4 3
101输出
3样例 2
输入
见选手目录下 tear/tear2.in
输出
见选手目录下 tear/tear2.ans
测试点约束
- subtask1 (20 pts) ：$n, m \leq 1000$。
- subtask2 (30 pts) ：$n, m \leq 10^6$。
- subtask3 (50 pts) ：$n \leq 10^9$ ，$m \leq 10^6$ ，$a, b, q < n$。保证 $a$ 与 $n$ 互质。