Submit | All submissions | Best solutions | Back to list |
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: | C C++ 4.3.2 CPP C99 JAVA PYTHON PYTHON3 PY_NBC |
Resource: | own problem, used for IIT Delhi ACM ICPC provincial contest 2010 |