### PROBLEM LINK:

**Author:** Deepansh Parmani

**Tester:** Karan Malhotra, Dushyant Singh

**Editorialist:** Deepansh Parmani

### DIFFICULTY:

EASY,

### PREREQUISITES:

Loops,Fibonacci

### PROBLEM:

Defining F(i) as F(i) = F(i-1) + 2*F(i-2) , given F(1) = a and F(2) = b find out F(i)%1000000007 t times

### QUICK EXPLANATION:

the numbers of occurrences of a and b in F(i) is itself a fibonacci series

### EXPLANATION:

If we observe the patter we will find that number of times a and b are present in F(i) is itself a a fibonacci sequence

```
F(1) = 1.a + 0.b
F(2) = 0.a + 1.b
F(3) = 2.a + 1.b
F(4) = 2.a + 3.b
F(5) = 6.a + 5.b
F(6) = 10.a + 11.b
.
.
.
```

1,0,2,2,6,10… and 0,1,1,3,5,11 are itself following the pattern i.e any number is sum of previous and twice the previous’s previous

let

hence number of times a is added is in F* will be - (times a in F[i-1]) + 2*(times a in F[i-2])

then \begin{equation} A[1] = 1 \space and \space A[2] = 0 \end{equation}

and \begin{equation} B[1] = 0 \space and \space B[2] = 1 \end{equation}

and

and

then we can precompute A* and B* upto to maximum value of n i.e is 10^5

then our ans is simply is (A*.a + B*.b)

Also we need to take mod with 1e9+7 at each step

### ALTERNATIVE SOLUTION:

This question can be solved using matrix exponentiation in O(log(n)). Using this method we can calculate F(i) where i upto 10^18 .More about Matrix Exponentiation . This is shown in testers solution

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

Author’s solution can be found here.

Tester’s solution(Karan Malhotra) can be found here.