P8022 [ONTAK2015] Cutting

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**.

The first line contains four integers $k, p, q, r$. The second line contains a digit string $N$ of length $k$.

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

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