for i (`dd`)../s/gp<<<"print(lift(Mod([1,1;1,0],10^9)^$i)[1,1])"