Problem link
Difficulty
EASY
Pre-requisites
modular exponentiation
Problem
Chef was feeling bored so he decided to create a pattern to play with. His pattern always has 1 as its first element. Then he chooses a number K as the second element. After selecting K as his second number he creates next element in the pattern by multiplying all previously existing elements of the pattern.
Now he asks for your help to find the Nth element in his pattern. As his number can be very large, so output modulo 109 + 7.
Solution
Observation 1
You can simply try to create a pattern for this problem.
- 1st number : 1
- 2nd number : K
- 3rd number : K
- 4th number : K2
- 5th number : K4
- 6th number : K8
So you can see now that 7th number wil be K16 and so on.
General Expressoin
So your expression will something of form a(2b) % mod.
Use Fermat’s theorem
Fermat’s theorem states that a(n - 1) % n = 1 where n is prime.
So you can write a(2b) % mod = a(2b % (mod - 1)) % mod.
Finding 2b % (mod - 1) can be done using binary exponentiation.
Time Complexity
O(log(N)) in computing answer for N^th number.
Tester’s solution: Will be added Later