Description

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.

Input Format

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

Output Format

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

3 5 3

33

Hint

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