P3702 [SDOI2017] Sequence Counting

Alice wants to obtain a sequence of length $n$, where all elements are positive integers not exceeding $m$, and the sum of these $n$ numbers is a multiple of $p$. Alice also wants at least one of these $n$ numbers to be a prime number. Alice wants to know how many sequences satisfy her requirements.

One line with three integers, $n, m, p$.

One line with a single number: the number of sequences that satisfy Alice’s requirements, taken modulo $20170408$.

For $20\%$ of the testdata, $1 \leq n, m \leq 100$. For $50\%$ of the testdata, $1 \leq m \leq 100$. For $80\%$ of the testdata, $1 \leq m \leq 10^6$. For $100\%$ of the testdata, $1 \leq n \leq 10^9, 1 \leq m \leq 2 \times 10^7, 1 \leq p \leq 100$. Translated by ChatGPT 5