# All the matrices used
# in Fib generation
# has the form:
# [a b]
# [b c]
 
# [a b] \/ [a b] -- [a*a+b*b a*b+b*c]
# [b c] /\ [b c] -- [a*b+b*c b*b+c*c]
 
# F(2n) = (F(n-1) + F(n+1)) * F(n)
 
# [a b] \/ [1 1] -- [a+b a]
# [b c] /\ [1 0] -- [b+c b]
 
def fast_matrix_pow(n):
    if n==0: return [1,0,1]
    [a,b,c] = fast_matrix_pow(n>>1)
    tmp = b*b
    a,b,c = a*a+tmp, (a+c)*b, tmp+c*c
    if n%2 == 1:
        return [a+b,a,b]
    else:
        return [a,b,c]
 
def fast_fib(n):
    return fast_matrix_pow(n)[1]
 
print ([[fast_fib(x) for x in range(71)] for _ in range(1000)][-1])

IyBBbGwgdGhlIG1hdHJpY2VzIHVzZWQKIyBpbiBGaWIgZ2VuZXJhdGlvbgojIGhhcyB0aGUgZm9ybToKIyBbYSBiXQojIFtiIGNdCgojIFthIGJdIFwvIFthIGJdIC0tIFthKmErYipiIGEqYitiKmNdCiMgW2IgY10gL1wgW2IgY10gLS0gW2EqYitiKmMgYipiK2MqY10KCiMgRigybikgPSAoRihuLTEpICsgRihuKzEpKSAqIEYobikKCiMgW2EgYl0gXC8gWzEgMV0gLS0gW2ErYiBhXQojIFtiIGNdIC9cIFsxIDBdIC0tIFtiK2MgYl0KCmRlZiBmYXN0X21hdHJpeF9wb3cobik6CiAgICBpZiBuPT0wOiByZXR1cm4gWzEsMCwxXQogICAgW2EsYixjXSA9IGZhc3RfbWF0cml4X3BvdyhuPj4xKQogICAgdG1wID0gYipiCiAgICBhLGIsYyA9IGEqYSt0bXAsIChhK2MpKmIsIHRtcCtjKmMKICAgIGlmIG4lMiA9PSAxOgogICAgICAgIHJldHVybiBbYStiLGEsYl0KICAgIGVsc2U6CiAgICAgICAgcmV0dXJuIFthLGIsY10KCmRlZiBmYXN0X2ZpYihuKToKICAgIHJldHVybiBmYXN0X21hdHJpeF9wb3cobilbMV0KCnByaW50IChbW2Zhc3RfZmliKHgpIGZvciB4IGluIHJhbmdlKDcxKV0gZm9yIF8gaW4gcmFuZ2UoMTAwMCldWy0xXSk=