### PROBLEM LINK:

**Author:** Md Shahid

**Tester:** Md Shahid

**Editorialist:** Md Shahid

### DIFFICULTY:

EASY

### PREREQUISITES:

Maths, GP Series,

### PROBLEM:

Given **H**, you need to print the sum of the series **1 + 7 ^{1} + 7^{2} + … + 7^{H}**. Since the result can be large, the answer should be printed modulo

**10**.

^{9}+ 7### QUICK EXPLANATION:

Since the value of **H** is large, you need to use modular exponentiation to calculate the sum of the series. After calculating the numerator of the gp series, it should be divided by **6**, which can done by multiplying with the modular inverse of 6.

### EXPLANATION:

First we need to calculate the sum of the GP series given in the problem. We can do this by using the simple GP formula as

7^0+7^1+7^2+...+7^H = \cfrac {7^{H+1} - 1} {7-1}

But since **H** can be very large we can’t calculate this directly. We need to calculate the term **7 ^{H+1} ** of the numerator by using modular exponentiation. Then we need to subtract 1 from the result we calculated. Now we divide the numerator by

**7 – 1 = 6**, but as we are calculating the result MOD

**10**, we need to multiply the numerator by the modular multiplicative inverse of

^{9}+ 7**6**. Basically we need to find a number

**k**such that

6k\;\equiv\;1\;\;(mod\;\;10^9+7)

Then k will be the modular multiplicative inverse of 6. We can use Fermat’s Little Theorem to calculate the value of **k**. By the theorem, if **p** is any prime number, then for any integer **a ≤ p**, we can write

a^{p-1}\;\equiv\;1\;\;(mod\;\;p)

From here we get that

a^{p-2}\;\equiv\;a^{-1}\;\;(mod\;\;p)

k\;\equiv\;6^{10^9+5}\;\;(mod\;\;10^9+7)

As before we will find **k** using the modular exponentiation we used earlier. Now we just need to multiply this **k** with the numerator we obtained in the earlier steps and get the result. You can find the solution below for implementation details.

### AUTHOR’S AND EDITORIALIST’S SOLUTIONS:

Author’s and editorialist’s solution can be found here.

Tags:- ENCODING PROFBL modularexponentiation series gp dshahid380