class Fibonacci {
static final int MOD=1000000007;
public static void main
(String args
[]) {
int a=3,b=4,n = 46;
System.
out.
println(solution
(a,b,n
)); }
static int fib(int a,int b,int n)
{
int F[][] = new int[][]{{1,1},{1,0}};
if (n == 0)
return 0;
power(F, n-1);
long ans=(((a%MOD)*(F[0][1]%MOD))%MOD+ (b%MOD)*(F[0][0]%MOD)%MOD)%MOD;
return (int)(ans);
}
/* Helper function that multiplies 2 matrices F and M of size 2*2, and
puts the multiplication result back to F[][] */
static void multiply(int F[][], int M[][])
{/*
int x = (((F[0][0]%MOD)*(M[0][0]%MOD)%MOD) + (((F[0][1]%MOD)*(M[1][0]%MOD))%MOD))%MOD;
int y=(((F[0][0]%MOD)*(M[0][1]%MOD)%MOD) + (((F[0][1]%MOD)*(M[1][1]%MOD))%MOD))%MOD;
int z=(((F[1][0]%MOD)*(M[0][0]%MOD)%MOD) + (((F[1][1]%MOD)*(M[1][0]%MOD))%MOD))%MOD;
int w=(((F[1][0]%MOD)*(M[0][1]%MOD)%MOD) + (((F[1][1]%MOD)*(M[1][1]%MOD))%MOD))%MOD;
*/
int x = ((F[0][0]*M[0][0])%MOD + (F[0][1]*M[1][0])%MOD)%MOD;
int y = ((F[0][0]*M[0][1])%MOD + (F[0][1]*M[1][1])%MOD)%MOD;
int z = ((F[1][0]*M[0][0])%MOD + (F[1][1]*M[1][0])%MOD)%MOD;
int w = ((F[1][0]*M[0][1])%MOD + (F[1][1]*M[1][1])%MOD)%MOD;
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
/* Helper function that calculates F[][] raise to the power n and puts the
result in F[][]
Note that this function is designed only for fib() and won't work as general
power function */
static void power(int F[][], int n)
{
int i;
int M[][] = new int[][]{{1,1},{1,0}};
// n - 1 times multiply the matrix to {{1,0},{0,1}}
for (i = 2; i <= n; i++)
multiply(F, M);
}
/* Driver program to test above function */
public static int solution(int A,int B,int N){
return fib(A,B,N);
}
}
Y2xhc3MgRmlib25hY2NpIHsKCiAgICBzdGF0aWMgZmluYWwgaW50IE1PRD0xMDAwMDAwMDA3OwoKCiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiAoU3RyaW5nIGFyZ3NbXSkKICAgIHsKICAgICAgICBpbnQgYT0zLGI9NCxuID0gNDY7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKHNvbHV0aW9uKGEsYixuKSk7CiAgICB9CiAgICAgICAgCiAgICBzdGF0aWMgaW50IGZpYihpbnQgYSxpbnQgYixpbnQgbikKICAgIHsKICAgICAgICBpbnQgRltdW10gPSBuZXcgaW50W11bXXt7MSwxfSx7MSwwfX07CiAgICAgICAgaWYgKG4gPT0gMCkKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgcG93ZXIoRiwgbi0xKTsKCiAgICAgICAgbG9uZyBhbnM9KCgoYSVNT0QpKihGWzBdWzFdJU1PRCkpJU1PRCsgKGIlTU9EKSooRlswXVswXSVNT0QpJU1PRCklTU9EOwoKICAgICAgICByZXR1cm4gKGludCkoYW5zKTsKICAgIH0KCiAgICAvKiBIZWxwZXIgZnVuY3Rpb24gdGhhdCBtdWx0aXBsaWVzIDIgbWF0cmljZXMgRiBhbmQgTSBvZiBzaXplIDIqMiwgYW5kCiAgICBwdXRzIHRoZSBtdWx0aXBsaWNhdGlvbiByZXN1bHQgYmFjayB0byBGW11bXSAqLwogICAgc3RhdGljIHZvaWQgbXVsdGlwbHkoaW50IEZbXVtdLCBpbnQgTVtdW10pCiAgICB7LyoKICAgICAgICBpbnQgeCA9ICAoKChGWzBdWzBdJU1PRCkqKE1bMF1bMF0lTU9EKSVNT0QpICsgKCgoRlswXVsxXSVNT0QpKihNWzFdWzBdJU1PRCkpJU1PRCkpJU1PRDsKICAgICAgICBpbnQgeT0oKChGWzBdWzBdJU1PRCkqKE1bMF1bMV0lTU9EKSVNT0QpICsgKCgoRlswXVsxXSVNT0QpKihNWzFdWzFdJU1PRCkpJU1PRCkpJU1PRDsKICAgICAgICBpbnQgej0oKChGWzFdWzBdJU1PRCkqKE1bMF1bMF0lTU9EKSVNT0QpICsgKCgoRlsxXVsxXSVNT0QpKihNWzFdWzBdJU1PRCkpJU1PRCkpJU1PRDsKICAgICAgICBpbnQgdz0oKChGWzFdWzBdJU1PRCkqKE1bMF1bMV0lTU9EKSVNT0QpICsgKCgoRlsxXVsxXSVNT0QpKihNWzFdWzFdJU1PRCkpJU1PRCkpJU1PRDsKICAgICAqLwogICAgICAgIGludCB4ID0gICgoRlswXVswXSpNWzBdWzBdKSVNT0QgKyAoRlswXVsxXSpNWzFdWzBdKSVNT0QpJU1PRDsKICAgICAgICBpbnQgeSA9ICAoKEZbMF1bMF0qTVswXVsxXSklTU9EICsgKEZbMF1bMV0qTVsxXVsxXSklTU9EKSVNT0Q7CiAgICAgICAgaW50IHogPSAgKChGWzFdWzBdKk1bMF1bMF0pJU1PRCArIChGWzFdWzFdKk1bMV1bMF0pJU1PRCklTU9EOwogICAgICAgIGludCB3ID0gICgoRlsxXVswXSpNWzBdWzFdKSVNT0QgKyAoRlsxXVsxXSpNWzFdWzFdKSVNT0QpJU1PRDsKCiAgICAgICAgRlswXVswXSA9IHg7CiAgICAgICAgRlswXVsxXSA9IHk7CiAgICAgICAgRlsxXVswXSA9IHo7CiAgICAgICAgRlsxXVsxXSA9IHc7CiAgICB9CgogICAgLyogSGVscGVyIGZ1bmN0aW9uIHRoYXQgY2FsY3VsYXRlcyBGW11bXSByYWlzZSB0byB0aGUgcG93ZXIgbiBhbmQgcHV0cyB0aGUKICAgIHJlc3VsdCBpbiBGW11bXQogICAgTm90ZSB0aGF0IHRoaXMgZnVuY3Rpb24gaXMgZGVzaWduZWQgb25seSBmb3IgZmliKCkgYW5kIHdvbid0IHdvcmsgYXMgZ2VuZXJhbAogICAgcG93ZXIgZnVuY3Rpb24gKi8KICAgIHN0YXRpYyB2b2lkIHBvd2VyKGludCBGW11bXSwgaW50IG4pCiAgICB7CiAgICAgICAgaW50IGk7CiAgICAgICAgaW50IE1bXVtdID0gbmV3IGludFtdW117ezEsMX0sezEsMH19OwoKICAgICAgICAvLyBuIC0gMSB0aW1lcyBtdWx0aXBseSB0aGUgbWF0cml4IHRvIHt7MSwwfSx7MCwxfX0KICAgICAgICBmb3IgKGkgPSAyOyBpIDw9IG47IGkrKykKICAgICAgICAgICAgbXVsdGlwbHkoRiwgTSk7CiAgICB9CgogICAgLyogRHJpdmVyIHByb2dyYW0gdG8gdGVzdCBhYm92ZSBmdW5jdGlvbiAqLwoKCgogICAgcHVibGljIHN0YXRpYyBpbnQgc29sdXRpb24oaW50IEEsaW50IEIsaW50IE4pewogICAgICAgICAgICByZXR1cm4gZmliKEEsQixOKTsKICAgIH0KfQ==