Making S with two cells

Time limit2sMemory limit128 MB

Summary

You start with cells holding a and b, repeatedly add one cell to the other, and must decide whether the value S can ever appear in either cell.

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

Problem

A computer has two memory cells named a and b, and each cell holds one integer. The computer runs two instructions, a+=b and b+=a. a+=b raises the value in a by the value in b, and b+=a raises the value in b by the value in a.

A program is a list of these two instructions, run in the order they are written. A program with no instructions at all still counts as a program.

You are given the starting values of a and b and a target value S. Decide whether some program leaves S in one of the two cells when it finishes.

Input

The first line contains a, b, and S, separated by spaces. ( $0 \le a, b, S \le 10^{18}$ )

Output

Print YES if some program leaves S in one of the two cells, and NO otherwise.

Examples3

Example 1
Input
```
1 2 3
```
Expected output
```
YES
```
Example 2
Input
```
3 4 5
```
Expected output
```
NO
```
Example 3
Input
```
3 4 17
```
Expected output
```
YES
```