Problem Description

Given a digit string $N$ of length $k$ and three prime numbers $p, q, r$, split $N$ into three non-empty substrings such that the first substring is divisible by $p$, the second substring is divisible by $q$, and the third substring is divisible by $r$, and none of the three substrings has a leading $0$.

Note: A single digit $0$ is allowed.

Input Format

The first line contains four integers $k, p, q, r$.

The second line contains a digit string $N$ of length $k$.

Output Format

Output one integer, the total number of valid splitting ways.

19 2017 2027 2029
2017202741127832029

2

Hint

For $100\%$ of the testdata, $1 \leq k \leq 10^6$, $2015 < p, q, r \leq 10^5$, and $p, q, r$ are prime numbers.

Translated by ChatGPT 5