until(print(lift(Mod([1,1;1,0],10^9)^input)[1,1]),)