Коля разрабатывает интересную игру — экономический симулятор. Разумеется, его любимая часть разработки — это внутриигровое тестирование. Однажды он так увлекся этим процессом, что не заметил, как у него на счету осталось ровно 0 игровых монет.

Коля точно помнит, что в начале игры у него было n монет и что в процессе игры он покупал только дома за 1 234 567 монет, машины за 123 456 монет и компьютеры за 1234 монет.

Теперь он заинтересовался, мог ли он, покупая только дома, машины и компьютеры, потратить все свои игровые монеты, или же в игре есть баг? Формально: существуют ли целые неотрицательные числа a, b и c, такие что a × 1234567 + b × 123456 + c × 1234 = n?

Помогите Коле ответить на этот вопрос.