Movement 3

Interview

Time limit2sMemory limit512 MB

Summary

Decide whether (x, y) is reachable by moving 3^k right or up on each step k, starting at the origin.

Level: Medium5 of 10
Topics: Math, Bit manipulation, Recursion
Solved: No attempts yet

Problem

Donghyuk stands at the origin $(0, 0)$ of an infinitely large plane.

He moves toward $(x, y)$ one step at a time. Steps are numbered from $0$ , and the number goes up by $1$ after each finished step.

On step $k$ he picks one of two directions, right (the direction in which $x$ grows) or up (the direction in which $y$ grows), and moves exactly $3^k$ in the direction he picked. He cannot stay in place and he cannot skip a step.

Once he arrives at $(x, y)$ he stops there. Given $x$ and $y$ , write a program that decides whether he can reach $(x, y)$ starting from $(0, 0)$ .

Input

The first line contains $x$ and $y$ , separated by a space. ( $0 \le x \le 10^9$ , $0 \le y \le 10^9$ )

Output

Print $1$ if $(x, y)$ can be reached from $(0, 0)$ , and $0$ otherwise.

Examples5

Example 1
Input
```
1 3
```
Expected output
```
1
```
Example 2
Input
```
1 1
```
Expected output
```
0
```
Example 3
Input
```
3 0
```
Expected output
```
0
```
Example 4
Input
```
1 9
```
Expected output
```
0
```
Example 5
Input
```
3 10
```
Expected output
```
1
```