Euler Totient Function Extended

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Euler totient function (denoted by phi(N)) for a positive integer N is defined as number of positive integers less than or equal N that are coprime to N
Let's generalize this concept of Euler totient function. For positive integer N let's write out the integers that are less than or equal to N and are coprime to N. We'll get a list of integers of the form A_{1}, A_{2}, ..., A_{M}, where M = phi(N). Let's denote E_{K}(N) = A_{1}^{K} + A_{2}^{K}+...+A_{M}^{K}. This way we obtain something more general version of Euler totient function, in particular, E_{0}(N) = phi(N) for every positive integer N.
Your task is to calculate E_{K}(N). As answer could be large, print your answer modulo 10^{9}+7
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space separated integers N and K.
Output
For each test case, output a single line containing the answer to the problem i.e. the value of E_{K}(N) modulo 10^{9}+7.
Constraints
 1 ≤ T ≤ 128
Subtask 1 (7 points):
 1 ≤ N ≤ 10^{4}
 0 ≤ K ≤ 10^{4}
Subtask 2 (10 points):
 1 ≤ N ≤ 10^{12}
 K = 0
Subtask 3 (28 points):
 1 ≤ N ≤ 10^{12}
 K = 1
Subtask 4 (55 points):
 1 ≤ N ≤ 10^{12}
 0 ≤ K ≤ 256
Example
Input: 2 10 1 7 0 Output: 20 6
Explanation
Example case 1. The numbers that are coprime to 10 are 1, 3, 7, 9. Their sum is 20.
Example case 2. 7 is a prime number, so any integer that is less than 7 is coprime to it.
Author:  xcwgf666 
Tester:  karanaggarwal 
Editorial  http://discuss.codechef.com/problems/XETF 
Tags  easymedium, inclusnexclusn, ltime23, xcwgf666 
Date Added:  21032015 
Time Limit:  4  6 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 