题目描述

给定 $n,m,k$，求

$$\sum^{n}_{i=1} \sum^{m}_{j=1} \gcd(i,j)^k\ \bmod(10^9+7) $$

输入格式

输入有多组数据，输入数据的第一行两个正整数 $T,k$，代表有 $T$ 组数据，$k$ 的意义如上所示。

下面第二行到第 $T+1$ 行，每行为两个正整数 $n,m$，其意义如上式所示。

输出格式

输出一个整数。

1 2
3 3 

20

数据规模与约定

对于 $100\%$ 的数据，$1\le n,m,k\le 5\times 10^6,1\le T\le 2000$。

题目来源

命题人：成都七中张耀楠，鸣谢 excited 上传。