program main
  implicit none
  integer, parameter :: p = selected_int_kind(30)
  integer, parameter :: pmax = 120
  integer(kind=p) :: r
  integer :: count, n
  integer(kind=p), dimension(0:pmax) :: cache
  do n=0, pmax
     count = 0
     cache (0:2) = [0, 1, 1]
     cache (3:) = -1
     r = fib (n)
     write (*,'(I4,I30,I4)') n, r, count
  end do
contains
  recursive function fib (n) result(r)
    integer, intent(in) :: n
    integer (kind=p) :: r
    count = count + 1
    if (cache(n) >= 0) then
       r = cache(n)
    else
       if (mod(n,2) == 1) then
          r = fib ((n+1)/2)**2 + fib ((n-1)/2)** 2
       else
          r = fib (n/2) * (fib(n/2-1) + fib(n/2+1))
       end if
       cache(n) = r
    end if
  end function fib
end program main