Stone Groups

Interview

Time limit2sMemory limit512 MB

Summary

Starting from stone counts A, B, C, repeatedly double the smaller of two unequal groups and subtract it from the larger; decide whether all three can become equal.

Level: Medium6 of 10
Topics: BFS, Math, Hash map, Simulation
Solved: No attempts yet

Problem

Kangho plays a game with stones. The stones sit in three groups holding $A$ , $B$ and $C$ stones. Kangho wants all three groups to hold the same number of stones.

He moves stones one step at a time, and a step works like this.

Pick two groups whose stone counts differ.
Call the smaller count $X$ and the larger count $Y$ .
Change the smaller group to $X+X$ stones and the larger group to $Y-X$ stones.

Write a program that prints 1 if repeating the step any number of times can make the three groups hold the same number of stones, and 0 otherwise.

Input

The first line contains $A$ , $B$ and $C$ separated by spaces. ( $1 \le A, B, C \le 500$ )

Output

Print 1 if the three groups can be made to hold the same number of stones, and 0 otherwise.

Examples3

Example 1
Input
```
10 15 35
```
Expected output
```
1
```
Example 2
Input
```
1 1 2
```
Expected output
```
0
```
Example 3
Input
```
1 1 1
```
Expected output
```
1
```