;; Authors: Kate, Ben, and Monica
;;
;; n = input()
;; print fib(n)
;; def fib(n):
;;     if n <= 1:
;;         return n
;;     else:
;;         return fib(n-1) + fib(n-2)

    allocate-registers n fib baseCase sp zero one two cont test ans prevAns
    read n
    li fib Lfib
    li baseCase LbaseCase
    li sp 0
    li zero 0
    li one 1
    li two 2
    li cont LafterFib
    j fib
LafterFib:
    write ans
    halt

Lfib:
    sgt test n one
    jeqz test baseCase

    st cont sp
    add sp sp one
    st n sp
    add sp sp one

    sub n n one
    li cont LafterFirstCall
    j fib
    
LafterFirstCall:
    sub sp sp one
    ld n sp
    sub sp sp one
    ld cont sp

    st ans sp
    add sp sp one
    st cont sp
    add sp sp one
    st n sp
    add sp sp one

    sub n n two
    li cont LafterSecondCall
    j fib

LafterSecondCall:
    sub sp sp one
    ld n sp
    sub sp sp one
    ld cont sp
    sub sp sp one
    ld prevAns sp

    add ans ans prevAns
    j cont

LbaseCase:
    add ans n zero
    j cont