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


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

hide comments
2016-07-10 12:07:53
Learnt some new things, use modular exponentiation for faster power calculation
AC 2.03s in third attempt , after 2 TLEs.
A much recommended problem.
2015-11-14 20:57:43 newbie
easy one just simple logic is enough :)
2015-01-15 07:35:44 Malinga
consider ** times=b/i - (a-1)/i ** caused me two WA..
2014-12-30 08:36:52 Yashpal
O(sqrt(b)+sqrt(a))logn giving AC in 15 Sec .. :(
Any sort of Optimization ??

Last edit: 2014-12-30 08:37:09
2014-09-29 16:05:00 Bharath Reddy
Got AC with a generic implementation.
No need of code optimizations. A good algorithm is enough
Hint: Look at the constraints closely :)

Last edit: 2014-09-29 16:11:46
2014-06-29 03:04:54 oye lakshman help plz
@lakshman is this the correct ans 299384888 also is there any fast algo for powersum
here is my code
<snip>
kindly help me

Last edit: 2022-08-10 15:16:16
2014-06-29 02:59:39 [Lakshman]
@crazzysuarez Have you tried this case
1
1 100000 9999

Last edit: 2014-06-29 03:02:14
2014-06-28 20:42:41 tyson
getting WA plz provide with some test case
@nikhil sub id 11848600
2014-04-20 09:46:59 Rishav Goyal
yay :DDDDDD finalyy AAAcCCCCC :)
2014-01-22 14:51:06 Prakhar Gupta
nlog(n) always giving TLE on running (10)


Last edit: 2014-02-23 14:08:36
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.