### 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 : K
^{2} - 5th number : K
^{4} - 6th number : K
^{8}

So you can see now that 7th number wil be K^{16} 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 2^{b} % (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