P8022 [ONTAK2015] Cięcie

题目描述

给定一个长度为 $n$ 的数字串 $S$ 以及三个质数 $p, q, r$，请你将 $S$ 划分为三段非空字符串，使得第一段能被 $p$ 整除，第二段能被 $q$ 整除，第三段能被 $r$ 整除，且每一段都不含前导 $0$。

注：单独的 $0$ 是允许的。

输入格式

第一行，四个整数 $n, p, q, r$；

第二行，长度为 $n$ 的数字串 $S$。

输出格式

输出一个整数，即合法的划分方案的总数。

输入输出样例 #1

输入 #1

19 2017 2027 2029
2017202741127832029

输出 #1

2

说明/提示

对于 $100\\%$ 的数据，$1 \leq n \leq 10^6$，$2015 < p, q, r \leq 10^5$，$p, q, r$ 为质数。