Problem Link : CodeChef: Practical coding for everyone

Using Basic Mathematics, equation can be converted as :

F(x) = F(x-1) + F(x-2) + F(x-1)*F(x-2)

F(x) = F(x-1) + F(x-2) + F(x-1)*F(x-2) + 1 – 1

F(x) = ( F(x-1) + 1 ) * (F(x-2) + 1 ) - 1

F(x) + 1 = ( F(x-1) + 1 ) * (F(x-2) + 1 )

Let G(x) = F(x) + 1

**G(x) = G(x-1) * G(x-2)**

Now in question F(0) = a , F(1) = b;

G(0) = a + 1

G(1) = b + 1

G(2) = (a + 1)*(b + 1)

G(3) = (G(2) * G(1)) = (a + 1)*(b + 1)*(b + 1)

G(4) = ((a + 1)^2) * ((b + 1)^3)

G(5) = ((a + 1)^3) * ((b + 1)^5)

On observation,

for any k, **G(k) = ((a + 1)^( (Kth – 1) fibonaci number)) * ((b + 1)^(Kth fibonaci number)**

Now the question reduces to calculate the power of a number

Since the bibonaci number is very large, Even the 100th fibonaci numbe has 21 digits so we cant the the fibonaci number

We have heard about **fermat little theorem,**

It states that

**(a^(p-1) ) % p = 1 where p is a prime number**

From quotient remainder theorem:

fib( n ) = k * (p-1) + (fib(n) % (p – 1))

Now using this :

( c^( fib(n) ) ) % p = ( c^((k)*(p-1)) ) % p * ( c ^ (fib(n) % (p – 1))) % p

can be written as : X = Y * Z

Z can be easily calculated as (fib(n) % (p – 1)) can be easily store in int datatype

Y = 1 using fermat therorem

Nth fibo num can be calculated using Matrix Exponentaion.

```
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
ll power(ll a, ll b){
if(b == 0){
return 1;
}
ll temp = power(a, b/2);
temp = (temp*temp)%MOD;
if(b % 2 != 0){
temp = temp * a;
}
return temp%MOD;
}
// matrix expo to calculate nth fibo in log n time
ll fib(ll n){
if(n == 0 || n == 1 || n == 5){
return n;
}
if(n == 2){
return 1;
}
n = n - 1;
ll a[2][2] = {1,1,1,0};
ll ans[2][2] = {1,0,0,1};
ll temp[2][2];
ll mod = MOD-1, i , j , k;
while(n){
if(n % 2 != 0){
for(i = 0; i < 2; i++){
for(j = 0; j < 2; j++){
temp[i][j] = 0;
for(k = 0 ; k < 2; k++){
temp[i][j] += a[i][k] * ans[k][j];
temp[i][j] %= mod;
}
}
}
for (i = 0; i < 2; i++)
{
for (j = 0; j < 2; j++)
{
ans[i][j] = temp[i][j];
}
}
}
for(i = 0; i < 2; i++){
for(j = 0; j < 2; j++){
temp[i][j] = 0;
for(k = 0; k < 2; k++){
temp[i][j] += a[i][k]*a[k][j];
temp[i][j] %= mod;
}
}
}
for(i = 0 ; i < 2; i++){
for(j = 0; j < 2; j++){
a[i][j] = temp[i][j];
}
}
n >>= 1;
}
return ans[0][0];
}
int main(){
ll test;
cin >> test;
while(test--){
ll a, b, n, c;
cin >> a >> b >> n;
if(n == 0){
cout << a << endl;
}
else if( n == 1){
cout << b << endl;
}
else{
ll x = fib(n-1);
ll y = fib(n);
c = power(a+1, x)* power(b+1, y);
c--;
c = c%MOD;
c = (c + MOD)%MOD;
cout << c << endl;
}
}
return 0;
}
```