Problem Chilly Willy

Link: http://codeforces.com/problemset/problem/248/B

B. Chilly Willy

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Chilly Willy loves playing with numbers. He only knows prime numbers that are digits yet. These numbers are 2, 3, 5 and 7. But Willy grew rather bored of such numbers, so he came up with a few games that were connected with them.

Chilly Willy wants to find the minimum number of length n, such that it is simultaneously divisible by all numbers Willy already knows (2, 3, 5 and 7). Help him with that.

A number's length is the number of digits in its decimal representation without leading zeros.

Input

A single input line contains a single integer n (1 ≤ n ≤ 10⁵).

Output

Print a single integer — the answer to the problem without leading zeroes, or "-1" (without the quotes), if the number that meet the problem condition does not exist.

Sample test(s)

input

1

output

-1

input

5

output

10080

Algorithm: Cài cộng với tham lam.
Code:

/*
Coder : Nguyen Duc Tam
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<utility>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>

using namespace std;

#define REP(i, start, end, step) for(int i = start; i < end; i += step)
#define DOWN(i, start, end, step) for(int i = start; i > end; i -= step)
#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())
#define X first
#define Y second

#define L(x,i) ((x) << (i))
#define R(x,i) ((x) >> (i))
#define AND(a,b) ((a) & (b))
#define OR(a,b) ((a) | (b))
#define XOR(a,b) ((a) ^ (b))
#define NOT(a) (~(a))
#define SB(x,i) (OR((x), L(1, (i)))) // x | 1 << i
#define CB(x,i) (AND((x),NOT(L(1,(i))))) // x & ~(1 << i)
#define TB(x,i) (AND((x), L(1,(i)))) // x & (1 << i)

#define FILL(a,val) memset(a,val,sizeof(a));
#define INIT(a,l,r,val) REP(i,l,r,1) (a)[i] = val;
#define DIG(c) (int)((c) - '0')
#define CHR(c) (char)((c) + '0')
#define LOW(c) (char)((c) + 32)
#define UPP(c) (char)((c) - 32)

#define EPS 1e-7
#define OO 1000000005
#define N 100005

const int DAY[13] = {-1,31,29,31,30,31,30,31,31,30,31,30,31};


typedef pair<int,int> II;
typedef pair<II,int> D;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned char UC;

int n;
int a[N];

int mod(int n, int pow, int div) // (n^pow) % div
{
if(pow == 0) return 1;
if(!(pow&1))
{
int temp = mod(n, pow / 2, div);
return (temp * temp) % div;
}
return (mod(n, pow - 1, div) * n) % div;
}

int div7(int x) //an an-1....a2 a1 % x
{
int temp = 0;
DOWN(i,n,1,1)
{
temp =(temp + (mod(10, i - 1, x) * a[i]) % x) % x;
}
return temp;
}

int main()
{
#define Off  true
if(Off)
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
}

cin >> n;
if(n < 3)
{
cout << "-1" << endl;
return 0;
}
a[1] = 0;
REP(i,2,n + 1,1)
a[i] = 0;
a[n] = 1;

int x = 2;

while(true)
{
int pos = 2;
int xx = x;
while(xx != 0)
{
a[pos] = xx % 10;
xx /= 10;
pos++;
}
if(div7(7) == 0 && div7(3) == 0)
{
break;
}
x++;
}

DOWN(i,n,0,1) printf("%d",a[i]);
cout << endl;

return 0;
}