A function is defined as follows :

GF(A,B,0)=A

GF(A,B,1)=B

GF(A,B,N)= GF(A,B,N-1)+GF(A,B,N-2) where N>1

Given 3 non negative numbers A B N returns remainder from division by 1000000007

For example given A =3 B=4 n =5 the function should return 29 BECAUSE

GF(3,4,0)= 3 mod 1000000007 = 3

GF(3,4,1)= 4 mod 1000000007 = 4

GF(3,4,2)= (GF(3,4,0)+GF(3,4,1)) mod 1000000007 =7

GF(3,4,3)= (GF(3,4,1)+GF(3,4,2)) mod 1000000007 =11

GF(3,4,4)= (GF(3,4,2)+GF(3,4,3)) mod 1000000007 =18

GF(3,4,5)= (GF(3,4,3)+GF(3,4,4)) mod 1000000007 =29

Can anyone solve this question in

time complexity: O(logN)

space complexity: O(1)