Sam-Sam-Han Number 2

Time limit1sMemory limit256 MB

Summary

Decide whether N can be written as a sum of distinct powers of 3, with at least one term, then print YES or NO.

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

Problem

Junha gets a sam-sam-han feeling when he sees a number that can be made using only powers of 3.

To state this feeling precisely, a number is called sam-sam-han if some number $x$ can be made by adding powers of 3, each used at most once, with no repetitions. A sam-sam-han number must contain at least one power of 3.

For example, 109 is sam-sam-han because it can be written as $3^0+3^3+3^4$ . But 7 and 18 are not sam-sam-han.

Junha wants to find out how many more sam-sam-han numbers there are.

Input

The first line contains a non-negative integer $N$ that is less than or equal to 9,223,372,036,854,775,807.

Output

If the given number is sam-sam-han, print YES. Otherwise, print NO.

Examples2

Example 1
Input
```
109
```
Expected output
```
YES
```
Example 2
Input
```
298
```
Expected output
```
NO
```