Codeforces Round #357 (Div. 2) B Economy Game（水题）

思路：水题，注意c为0这种情况即可

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	int flag = 0;
	scanf("%d",&n);
	for(int i = 0;i<100;i++)
	{
		for(int j = 0;j<1000;j++)
		{
			if(n-1234567*i-j*123456==0)
				flag=1;
			if(n-1234567*i-j*123456>=1234)
			{
				int res = n-1234567*i-j*123456;
				if(res%1234==0)
					flag=1;
			}
		}
	}
	if(flag)
		printf("YES\n");
	else
		printf("NO\n");
}

B. Economy Game

time limit per test

memory limit per test

input

output

0.

n and that he have bought only some houses (for1 234 567 game-coins each), cars (for 123 456 game-coins each) and computers (for 1 234

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 thata × 1 234 567 + b × 123 456 + c × 1 234 = n?

Please help Kolya answer this question.

Input

n (1 ≤ n ≤ 109) — Kolya's initial game-coin score.

Output

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

1 234 567 + 123 456 + 1234 = 1 359 257