3의 거듭제곱 합

3의 거듭제곱은 3^0, 3^1, 3^2, ...처럼 이어지며, 값은 차례대로 1, 3, 9, 27, ...이다.

서로 다른 3의 거듭제곱을 하나 이상 골라 더하면 여러 자연수를 만들 수 있다. 예를 들어 30은 27 + 3으로 만들 수 있으므로 이런 수에 포함된다.

이렇게 만들 수 있는 수들을 작은 것부터 정렬했을 때, N번째 수를 구하시오.

첫째 줄에 자연수 N이 주어진다.

N은 500,000,000,000 이하이다.

서로 다른 3의 거듭제곱을 하나 이상 더해 만들 수 있는 수 중에서 N번째로 작은 수를 출력한다.