Sums of Powers of Three

Interview

Time limit2sMemory limit128 MB

Summary

Given N, find the Nth smallest positive integer that is a sum of distinct powers of three, using a base-2 to base-3 digit mapping.

Level: Medium4 of 10
Topics: Math, Bit manipulation, Number theory
Solved: No attempts yet

Problem

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.

Input

The first line contains a positive integer N.

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

Output

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

Examples2

Example 1
Input
```
4
```
Expected output
```
9
```
Example 2
Input
```
1
```
Expected output
```
1
```