IITD4  Divisor Summation Powered
Define F(n,k) = Sum of kth powers of all divisors of n
So for example F(6,2) = 1^2 + 2^2 + 3^2 + 6^2 = 50
Define further G(a,b,k) as : Sum of F(j,k) where j varies from a to b both inclusive
Your task is to find G(a,b,k) given a,b & k.
As values of G can get very large , you only need to output the value of G(a,b,k) modulo 10^9+7.
Input Format:
First line of input file contains a single integer T  denoting the number of test cases.
The follow description of T test cases. Each test case occupies exactly one line which contains three space separated integers a,b & k.
Output Format:
Output your result for each test case in a new line.
Sample Input File:
2
2 2 1
1 3 2
Sample Output File:
3
16
Description of sample output:
In case 1, we are to find sum of divisors of 2. which is nothing but 1+2=3.
In case 2, we are to find sum of squares of divisors of 1 2 & 3. So for 1 sum is = 1. For 2 sum is = 1^2+ 2^2= 5. For 3 sum is = 1^2 + 3^2=10.
So ans is 16.
Constraints :
1<=a<=b<=10^5
1<=k<=10^5
Number of test cases <=20
hide comments
rishabh_1997:
20160710 12:07:53
Learnt some new things, use modular exponentiation for faster power calculation


newbie:
20151114 20:57:43
easy one just simple logic is enough :) 

Malinga:
20150115 07:35:44
consider ** times=b/i  (a1)/i ** caused me two WA.. 

Yashpal:
20141230 08:36:52
O(sqrt(b)+sqrt(a))logn giving AC in 15 Sec .. :(


Bharath Reddy:
20140929 16:05:00
Got AC with a generic implementation.


oye lakshman help plz:
20140629 03:04:54
@lakshman is this the correct ans 299384888 also is there any fast algo for powersum


[Lakshman]:
20140629 02:59:39
@crazzysuarez Have you tried this case


tyson:
20140628 20:42:41
getting WA plz provide with some test case


Rishav Goyal:
20140420 09:46:59
yay :DDDDDD finalyy AAAcCCCCC :) 

Prakhar Gupta:
20140122 14:51:06
nlog(n) always giving TLE on running (10)

Added by:  Nikhil Garg 
Date:  20101015 
Time limit:  0.530s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 NODEJS OBJC VB.NET 
Resource:  own problem, used for IIT Delhi ACM ICPC provincial contest 2010 