Background

Standing on this wooden platform, it creaks and cracks. You take out all kinds of potions from your bag and drink them one by one. A warm feeling rises from the bottom of your heart. You take out the carefully prepared bait, which is condensed from the essence of three servants. You raise it high above your head, trying to lure out the god-eater. The sky begins to fill with a bluish-purple mist. This atmosphere presses on you until you can hardly breathe. In a daze, the space in front of you starts to tear open into a crack. A giant python covered in a purple shell crawls out of it. You pick up the greatsword in your hand. Listening to roar after roar, you know this will be a hard fight...

Problem Description

Please compute the value of:

$\sum_{i=1}^{n} \sum_{j=1}^{m}(i\times j \bmod p)$

where $n,m,p$ are given.

Input Format

One line with three positive integers $n,m,p$ separated by spaces, as described in the statement.

Output Format

Output one integer, the answer. Since the result may be very large, output it modulo $10^9+7$.

3 3 10

36

114514 1919810 233

696303234

Hint

[Sample Explanation #1]

It is obvious that $i\times j$ only has the following cases: $[1,2,3,2,4,6,3,6,9]$. The sum of these values is $36$.

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the testdata, $1\le n,m\le10^{12}$, $1\le p\le10^3$.

Translated by ChatGPT 5