program name
    implicit none
    integer(4):: k,i
    integer(4),allocatable:: r(:)
    character(1),allocatable:: ans(:)

    read*, k

    allocate(r(1))
    r(1) = 0


    do while(k > 0)
        k=k-1
        r(1) = up(1)
    end do


    allocate(ans(size(r)))
    do i=1,size(r)
        ans(size(r)-i+1) = char(r(i) + ichar('1')-1)
    end do
    print*, ans(:)
contains
recursive function up(k) result(ret)
    integer(4):: k
    integer(4):: ret
    integer(4),allocatable:: tmp(:)

    if (k+1 > size(r)) then
        if (r(k) <= 8) then
            ret = r(k)+1
            return
        else
            allocate(tmp(size(r)))
            tmp(:) = r(:)
            deallocate(r)
            allocate(r(size(tmp)+1))
            r(1:size(tmp)) = tmp(:)
            r(size(tmp)+1) = 1
            ret = 0
            return
        end if
    end if
    
    if (abs(r(k)+1 - r(k+1)) <= 1) then
        if (r(k) <= 8) then
            ret = r(k)+1
            return
        else
            r(k+1) = up(k+1)
            ret = max(0,r(k+1) -1)
            return
        end if
        
    end if

! 繰り上がり
    r(k+1) = up(k+1)
    ret = max(0,r(k+1) -1)

end function

end program name