### PROBLEM LINK:

**Author:** Arjun Bharat

**Tester:** Arjun Bharat

**Editorialist:** Arjun Bharat

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

Math, modular exponentiation

### PROBLEM:

Given the functional equation * f(x+1)=kf(x)+g(x), g(x+1)=kg(x)+f(x), f(0)=2 and g(0)=0*, the task

is to find the value of f(n)

*, where n and k are program inputs.*

**modulo 1000000007**### QUICK EXPLANATION:

This is achieved by first solving the equations to obtain: **f(x)= 2 ^{x}, if(k=1)**

**f(x)= (k+1)**^{x}+ (k-1)^{x}, for k>1.Then we compute the remainder using fast modular exponentiation which is best suited for the given constraints.

### EXPLANATION:

One may either add or subtract the two equations and obtain these following equations:

**f(x+1)-g(x-1)=(k-1)(f(x)-g(x)),**

**f(x+1)+g(x+1)=(k+1)(f(x)+g(x))**

Thus defining new functions **h(x)=f(x)+g(x)** and **p(x)=f(x)-g(x)**,

we have *p(x)=2*(k-1)^{x}*, h(x)=2(k+1)^{x}.*

Substituting any one of them back will yield

*, and thus*

**f(x+1)=(k+1)f(x)-(k-1)**^{x}by superposition of the homogeneous and particular solutions to the recursive relation, set

*, solving gives a=b=1.*

**f(x)=a(k+1)**^{x}+ b(k-1)^{x</sup}Thus we have

*.*

**f(x)=(k+1)**^{}+ (k-1)^{x}Now we proceed to obtain the remainder.

Notice that using a linear recurrence,

**ans(n)=(k * ans(n-1))%M**is O(n) and will not pass in under one second.

We proceed to use fast modular exponentiation. A brief snippet coded in C++ is highlighted below:

long long fn(long long n,long long k)

{

if(n==0)

return 1;

else if(n==1)

return k;

else if(n%2==0)

{

long long y = fn(n/2,k);

return ((y%M)*(y%M))%M;

}

else

{

long long z= fn(n/2,k);

return ((y%M)*(y%M)*(k))%M;

}

}

long long ans = fn(n,k+1)+fn(n,k-1);

ans%=M;//M=10^9+7

//This code works even when k=0, as the second call returns 0.

This is O(lg n), a marked improvement.

### ALTERNATIVE SOLUTION:

The trivial solution is to use a linear recurrence as described earlier, which is not suitable based on program constraints.

Manually computing and storing f(x) and g(x) values, with or without modulo is

not advisable due to their large magnitudes, and the linear time complexity involved therein.

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

Author’s solution can be found here: jdoodle.com/a/wPF

### RELATED PROBLEMS:

TOPTWO