[ONTAK2015] Cięcie

题目描述

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

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

输入格式

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

第二行，长度为 $k$ 的数字串 $N$。

输出格式

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

样例 #1

样例输入 #1

19 2017 2027 2029
2017202741127832029

样例输出 #1

2

提示

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