Age Expression

Time limit5sMemory limit1024 MB

Summary

Given Dr. O's age N and the ages A and K of his granddaughters, decide whether positive integers a and k satisfy a*A + k*K = N.

Level: Easy2 of 10
Topics: Brute force, Math
Solved: No attempts yet

Problem

Dr. O has two granddaughters, Alyssa and Konari, and they keep Dr. O young!

When people ask Dr. O how old he is, Dr. O does not give one positive integer (his age). Instead, Dr. O gives two positive integers $a$ and $k$ . Dr. O's age is then computed as $(a \times \text{Alyssa's age}) + (k \times \text{Konari's age})$ .

Given three positive integers (Dr. O's age, Alyssa's age, and Konari's age), determine whether positive integers $a$ and $k$ exist.

Input

There is one input line with three integers, in order: Dr. O's age, Alyssa's age, and Konari's age. It is given that $1 \leq$ Konari's age $<$ Alyssa's age $<$ Dr. O's age $\leq 150$ .

Output

Print 1 if $a$ and $k$ exist, and 0 otherwise. Note that $a$ and $k$ must both be greater than zero.

Examples5

Example 1
Input
```
69 9 1
```
Expected output
```
1
```
Example 2
Input
```
76 11 7
```
Expected output
```
1
```
Example 3
Input
```
50 9 3
```
Expected output
```
0
```
Example 4
Input
```
70 10 5
```
Expected output
```
1
```
Example 5
Input
```
10 7 2
```
Expected output
```
0
```