Background

A contest needs an easy check-in problem.

Problem Description

Leasier was caught playing Minecraft, so he had to compute the value of the following expression.

$$\displaystyle\sum_{i = 1}^n \sum_{j = 1}^m \tau(i) \tau(j) \tau(\gcd(i, j))$$

Since the result may be very large, you only need to output the value modulo $p$.

If you have questions about the mathematical symbols in this problem, please check the "Hint" section.

Input Format

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

Output Format

One line with one integer, representing the required value.

5 7 9

5

Hint

Constraints and Notes

This problem uses bundled testdata.

Subtask	$n, m$	Score
$1$	$1 \leq n, m \leq 10^3$	$15 \operatorname{pts}$
$2$	$1 \leq n, m \leq 10^5$	$25 \operatorname{pts}$
$3$	$1 \leq n, m \leq 10^6$	$30 \operatorname{pts}$
$4$	No special constraints

For $100\%$ of the testdata, $1 \leq n, m \leq 2 \times 10^6$, and $1 \leq p \leq 10^9$.

Hint

As a beginner-friendly check-in problem, of course hints are provided.

• $\sum$ is the summation symbol. For example, $\displaystyle\sum_{i = 1}^n i$ means $1 + 2 + \cdots + n$.
• $\tau$ denotes the number of divisors. For example, $\tau(6) = 4$.
• $\gcd$ is the greatest common divisor. For example, $\gcd(12, 15) = 3$.

Notes

Minecraft OI Round 2 A

• Maker: Leasier
• Tester: happydef

Translated by ChatGPT 5