フィボナッチ数列の各項下3桁のみからなる数列の一般項

a[0]=0
a[1]=1
a[i]=(a[i-1]+a[i-2]) mod 1000, i ≧ 2

素直に計算しても答は簡単に求まる。

しかし，各項は高々 3 桁なのだから，m 項が 0 で，m+1 項が 1 になることもあるだろうと...
実際に調べれば，m = 1500 とわかる。
つまり一般項 a[n] は，a[n] = a[n mod 1500] ということ。
素直に考えるだけじゃダメという訳か。