Prime-Infused Sequence Count

Alice wants to form a sequence of length \(n\) such that each element is a positive integer not exceeding \(m\). The sum of the \(n\) numbers must be a multiple of \(p\). Furthermore, at least one of the numbers in the sequence must be a prime number.

Determine how many such sequences exist. Since the answer can be large, output the answer modulo \(10^9+7\).

Note: A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself.

inputFormat

The input consists of a single line containing three integers \(n\), \(m\), and \(p\) separated by spaces.

• \(n\): the length of the sequence.
• \(m\): the maximum value each element can have (each element is between 1 and \(m\)).
• \(p\): the divisor for the sum condition.

outputFormat

Output a single integer representing the count of sequences satisfying the conditions, modulo \(10^9+7\).

sample

1 5 3

1