Fafa Grid Sum

Given three positive integers \(n\), \(R\) and \(P\), consider all sequences \(\{a_i\}_{i=1}^{n}\) where each \(a_i\) is an integer in the range \([1, R]\). For each such sequence, we create an \(n \times n\) grid \(G\) where the entry in cell \((i,j)\) is defined as

[ G_{i,j} = a_i \times a_j \pmod{P}. ]

Define the "Fafa value" of a grid as the number of distinct values present in \(G\). In other words, if \(S\) is the set of distinct numbers in \(G\), then the Fafa value is \(|S|\).

Your task is to compute the sum of the Fafa values over all possible sequences, and output the result modulo \(10^9+7\). That is, let \(F(a_1, a_2, \dots, a_n)\) be the Fafa value of the grid generated by the sequence. You need to find

[ \sum_{(a_1, a_2, \dots, a_n) \in [1,R]^n} F(a_1, a_2, \dots, a_n) \pmod{10^9+7}. ]

Note: The grid is completely determined by the multiset of numbers in the sequence. In particular, if \(S\) is the set of distinct elements in the sequence, then the grid's entries are exactly all values \(x \times y \pmod{P}\) where \(x, y \in S\).

inputFormat

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

\(1 \le n \le \text{small}\), \(1 \le R \le \text{small}\), \(P \) is a positive integer.

outputFormat

Output a single integer, indicating the sum of the Fafa values over all \(n\)-length sequences, taken modulo \(10^9+7\).

sample

3 3 5

75