于神之怒加强版

题目描述

给定 $n,m,k$,计算 $$\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k$$ 对 $10^9 + 7$ 取模的结果。

输入输出格式

输入格式


**本题单测试点内有多组测试数据**。 第一行有两个整数,分别表示数据组数 $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$。