Description 给下N,M,K.求 ∑i=1n∑j=1mgcd(i,j)kmod(109+7) \sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k mod (10^9+7) Input 输入有多组数据，输入数据的第一行两个正整数T,K，代表有T组数据，K的意义如上所示，下面第二行到第T+1行，每行为两个正整数N,M，其意义如上式所示。

Description 给下N,M,K.求 Input 输入有多组数据，输入数据的第一行两个正整数T,K，代表有T组数据，K的意义如上所示，下面第二行到第T+1行，每行为两个正整数N,M，其意义如上式所示。 Output 如题 Sample Input 1 2 3 3 Sample Output 20 HINT 1<=N,M,K<=5000000,1<=T<=2000