IITD4 - Divisor Summation Powered

no tags 

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 and 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

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 and k.

Output

Output your result for each test case in a new line.

Sample

Input:
2
2 2 1
1 3 2

Output:
3
16

Description of Sample

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 and 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 answer is 16.

Constraints

1 <= a <= b <= 10^5

1 <= k <= 10^5

Number of test cases <= 20


hide comments
Rohan Garg: 2013-12-31 21:16:45

Java time limit should be increased. The same solution in C passed 7 seconds faster than the slowest solution in C/C++.

Divanshu: 2013-03-21 13:49:51

Optimisations required to AC !
Pheww, had to face many TLE's! :)

Last edit: 2013-03-21 13:50:22
praveen123: 2013-02-11 22:14:44

accepted after a lot of TLE's :)

god_father: 2013-01-23 20:27:09

really good question no need of any precompution...

Vikas Kushwaha: 2012-12-30 07:17:48

a very good problem.
learnt something new.
but there is no need of precomputation. :)

(Tjandra Satria Gunawan)(曾毅昆): 2012-10-06 13:19:56

easy, no precomputation or memoization needed to get AC, my semi-bruteForce program got AC!

blashyrkh: 2011-08-25 11:51:17

Not a lot really. Memorization of some intermediate results is enough to get AC.

P.S. nice problem indeed

sandeep pandey: 2011-04-25 20:20:44

nice problem.
try precomputation:-)

Last edit: 2011-08-31 11:37:51

Added by:Nikhil Garg
Date:2010-10-15
Time limit:1s
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