Роздвоєння#1972
Теоретичний фізик і математик працювали разом над задачею, яку описує певне рівняння. Одного дня математик схвильовано підійшов до фізика, повідомивши, що нарешті довів існування розв'язку їхнього рівняння.
"Друже мій," — відповів фізик, лагідно поплескавши його по плечу, — "якби я хоч колись засумнівався в існуванні розв'язку, я б уже давно перестав працювати над цією задачею!"
Діму часто розриває між його фізичною й математичною іпостасями. Його "фізик" стверджує, що Всесвіт, ймовірно, виник відповідно до законів імовірності, і з високою ймовірністю це твердження можна довести. Водночас його "математик" наполягає на суворому математичному доведенні цієї імовірнісної гіпотези виникнення.
Поки Діма зайнятий доведенням складної задачі з теорії ймовірностей, він просить тебе допомогти з простішою справою: "Чи існує невід'ємний цілий розв'язок рівняння ax + by = c при цілих коефіцієнтах?" Сам розв'язок Дімі не потрібен; його цікавить лише факт існування розв'язку, що підтримає його імовірнісний доказ дивовижної гіпотези. Тому він просить тебе вивести 1, якщо невід'ємний цілий розв'язок існує, і 0 — якщо ні.
Вхідні дані складаються з кількох тестових випадків, кількість яких заздалегідь невідома. Кожне рівняння подано окремим рядком у форматі:
ax + by = c
Тут коефіцієнти при та , що дорівнюють , опускаються (0 < a, b < 100000; |c| < 1000000).
Для кожного тестового випадку в окремому рядку виведіть 1, якщо задане рівняння має невід'ємний цілий розв'язок, інакше — 0.
Приклад 1