Hey in the hint he says to find the Ai fabonacii term

#1

hey in the hint he says to find the Ai fabonacii term …but Ai can be upto 10^9 and the 10^9th fabonacii term has apprx 10^8 digits…

#2

Hey this question uses a trick
GCD(Fib(A),Fib(B))=Fib(GCD(A,B))
Now you need to create a segment tree over A[i] and their GCD, now as A[i] is upto 10^9 its GCD will be definitely less than 10^9 so segment tree can be easily formed, after that we will need to use matrix exponentiation to find the Fib number. (under mod to prevent overflow.)

#3

Thnx ,I got it…thier hint videos r too confusing…