Sums of Powers of Three

The powers of three are 3^0, 3^1, 3^2, ..., whose values are 1, 3, 9, 27, ....

By choosing at least one distinct power of three and adding the chosen values, we can make certain positive integers. For example, 30 can be made as 27 + 3, so it belongs to this set.

When all numbers that can be made this way are sorted in increasing order, find the Nth number.

The first line contains a positive integer N.

N is at most 500,000,000,000.

Print the Nth smallest number that can be represented as the sum of one or more distinct powers of three.