Sparky is playing "Knights of X" and reaches the final battle with Knight of Numbers, Sir Countalot. The following challenge is given for the final battle :

A divisor d of a number N is a good divisor if GCD(d,N/d) = 1. Given integers N and K, Sparky has to find the sum of Kth powers of all good divisors of the factorial of N . Since the sum can be very large, Sparky has to find the sum modulo 1000000007.

Sir Countalot is cold and ruthless with his opponents. He steals Sparky's faithful sword Calculatibur so you must help Sparky beat the unscrupulous Knight Countalot with superior intelligence and speed.

Input format :

The first line of input contains a single integer T, the number of test cases.

Each of the next T lines contain two integers, N and K, corresponding to each test case.

Output format:

For each test case, output the required sum modulo 1000000007 in a separate line.

Constraints :

1 ≤ T ≤ 3

1 ≤ N ≤ 10^{7}

1 ≤ K ≤ 10^{18}

Sample Input :

2

3 4

4 2

Sample Output :

1394

650

ID

SUBMITTED AT

STATUS

LANGUAGE

TIME

MEMORY USED

USER

TIME

STATUS

LANGUAGE

TIME

MEMORY USED

7 months ago

cpp14

1.23 sec

39368 KB

7 months ago

cpp

1.57 sec

156716 KB

7 months ago

cpp

4.02 sec

78592 KB

7 months ago

cpp

0.07 sec

64 KB

7 months ago

cpp

4.01 sec

78592 KB