#Python 2, Sp3000 from fractions import* n=input() k,=P=[1] while n>len(P):k+=1;z=reduce(lambda x,y:x+y,P[~1:]);P+=[z]#*(gcd(z,k)<2) print P[-1]
Python 2, Sp3000
from fractions import* n=input() k,=P=[1] while n>len(P):k+=1;z=reduce(lambda x,y:x+y,P[~1:]);P+=[z]#*(gcd(z,k)<2) print P[-1]