### PROBLEM LINK:

**Author:** Avinash Verma

**Editorialist:** Avinash Verma

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

Modulo exponentiation

### PROBLEM:

Calculate the sum of all powers **(up to K)** of divisors for numbers from **l** to **r** modulo 10^9+7.

### QUICK EXPLANATION:

Calculate the contribution of every divisors of numbers from **l** to **r**. You will find **GP** sum for each divisor of all number from **l** to **r**.

### EXPLANATION:

Question asked you to calculate double summation, if we expand the formula then we see that for each divisors d of numbers from **l** to **r**, we have to add d^0 + d^1 + d^2 + d^3 +...+ d^K to our answer.

For each distinct divisors d of numbers form **l** to **r**, Lets say numbers of multiple of **d** from **l** to **r** is **multd**, then we will add ( d^0 + d^1 + d^2 + d^3 + . . . + d^K ) * multd to our answer for each divisors **d**.

As numbers can vary from **l** to **r**, divisors **d** can vary from **1** to **r**.

For each number **d** from **1** to **r**. we will calculate **multi_d** from this formula floor(r/d) – floor((l-1)/d) , where floor is a function to return integral part of any numbers.

We can calculate d^0 + d^1 + d^2 + . . . + d^K by GP sum formula i.e (d^{K+1}-1)/(d-1) .

Except for **d** equal to **1**, this formula is not appicable. For **d** equal to **1** GP sum is simply (K+1) .

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.