题目

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 ≤ 109) — 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

Input

1359257

Output

YES

Input

17851817

Output

NO

题解

暴力模拟妥妥的超时
换用动态规划

dp[i]表示i是否满足
当dp[i-1234]、dp[i-123456]、dp[i-1234567]中有任一个满足，则dp[i]满足

初始化dp[0]=0

由于n最大为1000000000,仍然是一个非常大的数字
仅仅打表就需要3、4秒
因此应该进一步优化

把1~1000000000输出发现:当n >= 27406118时，所有的都是YES
因此我们的计算量又小了一个数量级。

这时再打表可以瞬间输出答案

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;

const long long A = 1234567;
const long long B = 123456;
const long long C = 1234;

const int maxn = 27406118;
bool dp[maxn];


bool Do() {

    int n;
    bool OK = false;

    if(scanf("%d",&n) == EOF)
        return false;

    

    /*for(long long i = 0;(i*C <= n) && !OK;i++) {
        for(long long j = 0;(i*C + j*B <= n) && !OK;j++) {
            for(long long k = 0;(i*C + j*B + k*A <= n) && !OK;k++) {
                if(i*C + j*B + k*A == n) {
                    OK = true;
                    printf("%lld %lld %lld \n",i,j,k);
                }
            }
        }
    }*/
    if(n>=maxn||dp[n])
        printf("YES\n");
    else
        printf("NO\n");

    return true;
}

int main() {
    memset(dp,false,sizeof(dp));
    dp[0] = true;
    for(int i = 1;i < maxn;i++) {
        if((i - A >= 0 && dp[i - A]) || (i - B >= 0 && dp[i - B]) || (i - C >= 0 && dp[i - C]))
            dp[i] = true;
    }
    while(Do());
    return 0;
}