eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Раздвоение

Раздвоение

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Физик-теоретик и математик занимались одной и той же задачей, описываемой некоторым уравнением. Однажды математик с радостным видом подбежал к физику и сказал, что наконец-то сегодня он доказал, что уравнение, которым они занимаются, имеет решение.

- Дорогой мой, - ответил ему физик, снисходительно похлопав его по плечу, - если бы я хоть на минуту сомневался, что решение существует, то я бы давно перестал заниматься этой задачей!

В Диме постоянно происходит внутренняя борьба между Димой-физиком и Димой-математиком. Его физическая часть утверждает, что наш мир вероятней всего произошёл согласно законам теории вероятности и с большой долей вероятности можно утверждать, что подобное утверждение вероятней всего можно с большой долей вероятности доказать. В то же время его математическая часть требует строгого математического доказательства гипотезы вероятностного происхождения.

Так как Дима занят поисками математического доказательства невероятной проблемы в теории вероятности, он попросил Вас помочь ему в решении более простой задачи: "Имеет ли неотрицательное целочисленное решение при заданных целочисленных коэффициентах уравнение ax + by = c?". Так как для каждого уравнения ему не нужно само решение, а роль играет знание самого факта существования решения (именно это Дима будет использовать в вероятностном доказательстве своей невероятной гипотезы), он просит Вас вывести 1 в случае существования неотрицательного целочисленного решения и 0 в противном случае.

Входные данные

Входные данные содержат несколько тестовых случаев, количество которых заранее неизвестно. Каждое уравнение расположено в отдельной строке в виде

ax + by = c

причём коэффициенты при x и y равные 1 опускаются (0 < a, b < 100000; |c| < 1000000).

Для каждого тестового случая в отдельной строке выведите 1, если указанное решение заданного уравнения существует, и 0 в противном случае.

Пример

Входные данные #1
3x + 2y = 10
x + y = 0
35x + 15y = 67
Выходные данные #1
1
1
0