漸化式
a(n+1)+4a(n-1)=6a(n)
a(0)=2、a(1)=6
によって与えられる数列について
a(n)-1を1000で割ったあまりが答え。
周期p求めてn÷pのあまりを求める問題。
桁数はlog(n)オーダーでしか増えないので計算量もlog(n)オーダーでしか増えない。

同じ事だけどZ(√5)の整数環Rにおいての(3+√5)^nのR/1000Rの類だからどこか以降必ずループする。