P4619 [SDOI2018] Old Problem

- Input file: divsum.in - Output file: divsum.out - Time limit: 5 seconds - Memory limit: 512 megabytes (Note: The file input/output above was required during the contest. On Luogu, please use standard input/output.)

Time flies, and it is the NOI Qualifier season again... This is student $Q$'s second time taking the provincial team selection contest. This year, after learning a hard lesson, student $Q$ no longer takes the risk of stealing problems, but instead improves personal skills by practicing old problems. However, there are too many old problems. Student $Q$ works on them day and night, yet still cannot see where the light ahead is. One day, exhausted from doing too many problems, student $Q$ fell asleep and dreamed that, in the exam room, he encountered a problem that seemed familiar, but he could not remember how he had solved it before. Even after waking up, he was still frightened. Student $Q$ frowned, feeling that something was wrong, so he came to you and hoped you could teach him how to solve this problem. Student $Q$ vaguely remembered that the task was to compute the value of the following expression: $$ (\sum_{i=1}^{A}\sum_{j=1}^{B}\sum_{k=1}^{C}d(ijk))\bmod (10^9+7) $$ Here, $d(ijk)$ denotes the number of divisors of $i \times j \times k$.

The first line contains a positive integer $T$, meaning there are $T$ groups of testdata. The next $T$ lines each describe one group of testdata, containing three integers $A, B,$ and $C$, with meanings as described above.

For each group of testdata, output one line containing one integer, which is the value of the required expression.

For the testdata worth $30$ points, $1 \le A, B, C \le 5000$. For the testdata worth $100$ points, $1 \le T \le 10$, $1 \le A, B, C \le 10^5$, and $1 \le \sum \max(A, B, C) \le 2 \times 10^5$. Translated by ChatGPT 5