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^9) — 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).


-----Examples-----
Input
1359257

Output
YES
Input
17851817

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.

Difficulty: interview

Starter code:

Solutions:
3
# Copyright (C) 2016 Sayutin Dmitry.
#
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License as
# published by the Free Software Foundation; version 3
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program; If not, see <http://www.gnu.org/licenses/>.

def main():
    n = int(input())
    ans = False
    for a in range(0, 1001):
        for b in range(0, 1001):
            left = n - 1234567 * a - 123456 * b
            if left >= 0 and left % 1234 == 0:
                ans = True
    print("YES" if ans else "NO")

main()


n = int(input())
x = 1234567
y = 123456
z = 1234
for a in range(900):
    if a * x > n: break
    for b in range(9000):
        if a * x + b * y > n: break
        c = (n - a * x - b * y) // z
        if a * x + b * y + c * z == n:
            print('YES')
            return
print('NO')

from sys import *
n=int(input())
for a in range(n//1234567+1):
   for b in range((n-a*1234567)//123456+1):
      if (n-a*1234567-b*123456)%1234==0: print("YES"); return
print("NO")


n = int(input())
for a in range(2000):
    for b in range((n-1234567*a)//123456+50):
        rem = n - 1234567*a - 123456 * b
        if (rem%1234 == 0 and rem//1234 >= 0):
            print("YES")
            quit()
print("NO")


from collections import defaultdict, deque, Counter, OrderedDict
from bisect import insort, bisect_right, bisect_left
import threading, sys

def main():
    n = int(input())
    a = 1234567
    b = 123456
    c = 1234
    if n%2 != 0:
        n -= a
        if n < 0:
            print("NO")
            return
    for i in range(0,1000):
        now = a*i
        toc = n - now
        if toc < 0:
            print("NO")
            return
        j = 0
        while j*b <= toc:
            if (toc - j*b)%c == 0:
                print("YES")
                return
            j += 1



def __starting_point():
    """sys.setrecursionlimit(400000)
    threading.stack_size(40960000)"""
    thread = threading.Thread(target=main)
    thread.start()
__starting_point()

n = int(input())

for i in range(n // 1234567 + 1):
    ii = n - i * 1234567
    if ii == 0:
        print("YES")
        return
    for j in range(ii // 123456 + 1):
        jj = ii - j * 123456
        if jj == 0:
            print("YES")
            return
        if jj % 1234 == 0:
            print("YES")
            return

print("NO")

import sys

a, b, c = 1234567, 123456, 1234
n = int(input())
for aq in range(int(n // a) + 3):
    nn = n - a * aq
    if nn < 0: break
    for bq in range(int(nn // b) + 3):
        nnn = nn - b * bq
        if nnn < 0: continue
        if nnn % c == 0:
            print("YES")
            return
print("NO")

import sys


def main():
    x = 1234567
    y = 123456
    z = 1234
    s = int(sys.stdin.readline())
    if s % x ==0:
        print("YES")
        return

    while s >0 :
        if s % y ==0:
            print("YES")
            return
        s1 = s
        while s1 >0:
            if s1 % z ==0:
                print("YES")
                return
            s1-=y
        s-=x

    print("NO")

main()


n=int(input())


for nombre in range(0,n+1,1234567):
        for nombre2 in range(0,n+1,123456):
                reste=(n-nombre-nombre2)%1234
                diviseur=(n-nombre-nombre2)//1234
                if diviseur>=0 and reste==0:
                        print("YES")
                        return
print("NO")


import sys
def __starting_point():
    #n, m = list(map(int, input().split()))
    n = int(input())
    for i in range(n // 1234567 + 1):
        cur = n - i * 1234567
        for j in range(cur // 123456 + 1):
            if (cur - j * 123456) % 1234 == 0:
                print("YES")
                return
    print("NO")

__starting_point()

coin = int(input())

ans = "NO"

a = coin // 1234567

for x in range(a, -1, -1):
    b = (coin - (x*1234567)) // 123456

    for y in range(b, -1, -1):
        z = (coin - (x*1234567) - (y*123456)) // 1234

        if x*1234567 + y*123456 + z*1234 == coin:
            ans = "YES"
            break

        if ans == "YES":
            break

    if ans == "YES":
        break

print(ans)

HOUSE = 1234567
CAR = 123456
COMP = 1234

n = int(input())

answer = "NO"

for h in range(n//HOUSE+1):
    rest = n - h*HOUSE
    for c in range(rest//CAR+1):
        rest2 = rest - c*CAR
        if rest2 % COMP == 0:
            answer = "YES"
            break

print(answer)

n = int(input())

x, y, z = 1234567, 123456, 1234

a_max = n // x
b_max = n // y

# print(a_max, b_max)


def do_it():
    for a in range(a_max + 1):
        for b in range(b_max + 1):
            if a * x + b * y > n:
                break
            if (n - (a * x + b * y)) % z == 0:
                print('YES')
                return
    print('NO')

do_it()


import sys
import random

def test():
    for i in range(100):
        a, b, c = [random.randint(1, 20) for _ in range(3)]
        k = 1234567 * a + 123456 * b + 1234 * c
        assert k <= 1e9
        assert solve(k) == "YES"

def solve(n):
    for i in range(811):
        for j in range(8111):
            k = 1234567 * i + 123456 * j
            if k > n:
                break
            elif (k - n) % 1234 == 0:
                return "YES"
    return "NO"

n = int(input())
print(solve(n))


n=int(input())
yes=0
breaker=0
for a in range(n//1234567+1):
    for b in range((n-a*1234567)//123456+1):
        y = 1234567*a+123456*b
        if (n-y)%1234==0:
            yes=1
            print('YES')
            breaker=1
            break
    if breaker==1:
        break
if yes==0:
    print('NO')


from math import gcd

N = int(input())
x = 1234567
y = 123456
z = 1234

g = gcd(y, z)

if N % x == 0:
    print('YES')
    return

for a in range(N // x + 1):
    n = N - a * x

    if n % y == 0 or n % z == 0:
        print('YES')
        return
    if n % g != 0:
        continue

    x0 = -22 * n // 2
    y0 = 2201 * n // 2
    k = ((-x0) // (z // 2)) + 1
    x0 += k * z // 2
    y0 -= k * y // 2
    if y0 >= 0:
        print('YES')
        return

print('NO')


n = int(input())
sol = False
for i in range(max(n//1234567 + 1,1)):
    n2 = n - i*1234567
    for j in range(max(n2//123456 + 1, 1)):
        n3 = n2 - j*123456
        if n3 % 1234 == 0:
            sol = True
            break

print(["NO","YES"][sol])


n = int(input())

def tre(n):
    if n % 1234 == 0:
        return True
    return False

def dva(n):
    if n % 123456 == 0:
        return True
    else:
        k = n // 123456
        nn = n - k*123456
        for i in range (k, -1, -1):
            if tre(nn):
                return True
            nn += 123456
        return False

def one(n):
    if n % 1234567 == 0:
        return True
    else:
        kk = n // 1234567
        nnn = n - kk*1234567
        for i in range (kk, -1, -1):
            if dva(nnn):
                return True
            nnn += 1234567
        return False           


if n < 1234:
    print('NO')
elif n < 123456:
    if tre(n):
        print('YES')
    else:
        print('NO')
elif n < 1234567:
    if dva(n):
        print('YES')
    else:
        print('NO')
else:
    if one(n):
        print('YES')
    else:
        print('NO')
    
    
    


n = int(input())

ok = False

i = 0
while i * 1234567 <= n:
    j = 0
    while i * 1234567 + j * 123456 <= n:
        x = i * 1234567 + j * 123456

        if (n - x) % 1234 == 0:
            ok = True
            break
        j+=1
    if ok: break

    i+=1

print("YES" if ok else "NO")



n = int(input())

x = 1234567
y = 123456
z = 1234

if n < z:
    print("NO")
    return
else:
    a = 0
    while (a * x) <= n:
        b = 0
        while (b * y) + (a * x) <= n:
            if ((n - (b * y + a * x)) % z) == 0:
                print("YES")
                return
            b += 1
        a += 1

print("NO")

n = int(input())
A = 1234567
B = 123456
C = 1234
ans = 'NO'
for a in range(n // A + 1):
    for b in range((n - A * a) // B + 1):
        if (n - a * A - b * B) % C == 0 and n - a * A - b * B >= 0:
            ans = 'YES'
print(ans)

def main():
    n = int(input())
    x = 1234567
    y = 123456
    z = 1234
    for a in range(1000):
        for b in range(10000):
            c = (n - a * x - b * y) // z
            if c < -100: break
            if c >= 0 and a * x + b * y + c * z == n:
                print('YES')
                return
    print('NO')
main()

n = int(input())

br = False
for a in range(0, n + 1, 1234567):
    for b in range(0, n - a + 1, 123456):
        if (n - a - b) % 1234 == 0:
            print("YES")
            br = True
            break
    if br:
        break
else:
    print("NO")