A2719. 于神之怒加强版
编程题
省选/NOI-
知识点
题目描述
给定 $n,m,k$，计算
$$\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k$$
对 $10^9 + 7$ 取模的结果。
$$\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k$$
对 $10^9 + 7$ 取模的结果。
输入格式
**本题单测试点内有多组测试数据**。
第一行有两个整数，分别表示数据组数 $T$ 和给定的 $k$。
接下来 $T$ 行，每行两个整数，表示一组数据的 $n$ 和 $m$。
第一行有两个整数，分别表示数据组数 $T$ 和给定的 $k$。
接下来 $T$ 行，每行两个整数，表示一组数据的 $n$ 和 $m$。
输出格式
对于每组数据，输出一行一个整数表示答案。
输入输出样例
输入 #1
1 2 3 3
输出 #1
20
说明/提示
#### 数据规模与约定
对于全部的测试点，保证 $1 \leq T \leq 2 \times 10^3$，$1 \leq n, m, k \leq 5 \times 10^6$。
对于全部的测试点，保证 $1 \leq T \leq 2 \times 10^3$，$1 \leq n, m, k \leq 5 \times 10^6$。