Sam-sam Number

Interview

Time limit1sMemory limit256 MB

Summary

Decide whether N can be written as a sum of distinct powers of 3, using each power at most once.

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

Problem

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

To describe that feeling precisely: a number is sam-sam if some number $x$ can be made by adding powers of 3, each used at most once without overlap. A sam-sam number must contain at least one power of 3.

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

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

Input

The first line gives a nonnegative integer $N$ less than or equal to 2,147,483,647.

Output

Print YES if the given number is sam-sam, and NO otherwise.

Examples2

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