题目描述

对一个正整数 $s$ 反复执行以下过程 $n$ 次，会得到一个二进制字符串:

  s = [(a*s+c)/k] mod m
  if (s < [m/2]) 
    output 0
  else 
    output 1

其中 $[x]$ 表示不超过 $x$ 的最大整数。

给定一个二进制字符串$p$，请问一开始$s$有多少种不同的取值，可以问让输出的字符串恰好等于$p$？ （规定 $s$ 的取值范围：$0\leq s<m$）

输入格式

第一行：五个整数$a$，$c$，$k$，$m$，$n$。 第二行：$n$个字符，表示给定的二进制字符串 $p$。

输出格式

单个整数：表示满足条件的 $s$ 的初值的方案数。

7 3 10 10 10
0000000000

7

数据范围

• 对于 $50\%$ 的数据：$m\leq 10^4$，$n\leq 10^4$
• 对于 $100\%$ 的数据：$1\leq n\leq 10^5$，$1\leq m\leq 10^6$ $0\leq a< m$，$0\leq c< m$，$1\leq k\leq m$