#P4277. [ONTAK2015]Cięcie

    ID: 3495 传统题 1000ms 256MiB 尝试: 145 已通过: 53 难度: 6 上传者: 标签>难度分类普及+/提高-排序与序列处理前缀余数计数数论模逆元费马小定理快速幂模拟与实现技巧增量维护CF1900ByClaris

[ONTAK2015]Cięcie

[ONTAK2015] Cięcie

题目描述

给定长度为 kk 的十进制数字串 NN,以及三个质数 p,q,rp,q,r。在数字串中选两个切分位置,把整串依次分成三段非空连续子串。

三段作为十进制整数时,必须分别能被 p,q,rp,q,r 整除。每段都不能有前导零,单独一个 0 合法。求满足条件的切法数。不同的两个切分位置构成不同的切法。

输入格式

第一行四个整数 k,p,q,rk,p,q,r。第二行一个长度为 kk 的数字串 NN。

输出格式

输出一行一个整数,表示合法切法数。

样例 #1

样例输入 #1

19 2017 2027 2029
2017202741127832029

样例输出 #1

2

数据规模与约定

1≤k≤1061\le k\le10^6,2015<p,q,r≤1052015<p,q,r\le10^5,p,q,rp,q,r 都是质数。