P4449 Yu Shen's Fury Enhanced Edition

Given $n, m, k$, compute $$\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k$$ and output the result modulo $10^9 + 7$.

**There are multiple test cases in a single test file.** The first line contains two integers, the number of test cases $T$ and the given $k$. The next $T$ lines each contain two integers, $n$ and $m$, for one test case.

For each test case, output one line with a single integer representing the answer.

Constraints For all test points, it is guaranteed that $1 \leq T \leq 2 \times 10^3$, $1 \leq n, m, k \leq 5 \times 10^6$. Translated by ChatGPT 5