Economy Game

1000ms

262144K

Description:

Kolya is developing an economy simulator game. His most favourite part of the development process is in-game testing. Once he was entertained by the testing so much, that he found out his game-coin score become equal to 0.

Kolya remembers that at the beginning of the game his game-coin score was equal to n and that he have bought only some houses (for 1 234 567 game-coins each), cars (for 123 456 game-coins each) and computers (for 1 234 game-coins each).

Kolya is now interested, whether he could have spent all of his initial n game-coins buying only houses, cars and computers or there is a bug in the game. Formally, is there a triple of non-negative integers a, b and c such that a × 1 234 567 + b × 123 456 + c × 1 234 = n?

Please help Kolya answer this question.

Input:

The first line of the input contains a single integer n (1 ≤ n ≤ 10⁹) — Kolya's initial game-coin score.

Output:

Print "YES" (without quotes) if it's possible that Kolya spent all of his initial n coins buying only houses, cars and computers. Otherwise print "NO" (without quotes).

Sample Input:

Sample Output:

YES

Sample Input:

17851817

Sample Output:

NO

Note:

In the first sample, one of the possible solutions is to buy one house, one car and one computer, spending 1 234 567 + 123 456 + 1234 = 1 359 257 game-coins in total.

Informação

Provedor Codeforces

Código CF681B