[zerojudge] d828: Pascal's triangle's secret (II)

'''
依題意手算了幾個 n 發現是個 Fibonacci numbers
看到這種 n 很大，且要求取模輸出
猜想輸出的值大概會在 n 在某值時循環
google 發現是 Pisano period
網路上有求 Pisano period 的公式
此題我先算好 m = 10000, pisano = 15000
底下先建表，讀取測資後查表輸出
'''

from sys import stdin

f = [1,1,2,3,5,8]

pisano = 15000
for i in range(6, pisano):
    t = (f[-1]+f[-2])%10000
    f.append(t)

for s in stdin:
    n = int(s) % pisano
    print(f[n])