인간도

시간 제한1초메모리 제한1024 MB

요약
11을 제외한 두 자릿수 소수 N개를 이어 붙여 2N자리 수를 만들 때 11의 배수가 되도록 하거나 불가능하면 -1을 출력한다.
난이도

보통10점 중 6점

유형
수학, 정수론, 그리디, 구현
정답자
아직 제출이 없습니다

문제

인간도의 호반우들은 가장 좋아하는 소수인 1111을 제외하고 NN개의 두 자릿수 소수만을 사용하여 1111의 배수를 만들어야 한다.

정확히는 NN개의 두 자릿수 소수를 차례대로 이어 붙여 1111의 배수인 2N2N자리 수를 만들어야 한다. 같은 소수를 여러 번 사용해도 된다.

호반우를 도와 인간도에서 깨달음을 얻어보자.

입력

첫째 줄에 NN이 주어진다. (1≤N≤100,000)(1 \leq N \leq 100\\,000)

출력

만약 NN개의 두 자릿수 소수를 사용하여 1111의 배수를 만들 수 없다면 첫째 줄에 -1을 출력한다.

그렇지 않다면 첫째 줄에 두 자릿수 소수를 차례대로 이어붙여 만든 2N2N자리 수를 출력한다.

가능한 방법이 여러 가지라면 그중 아무거나 출력한다.

힌트

두 자릿수 소수로는 11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,9711, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 있다.

예제2

  1. 예제 1

    입력
    1
    
    예상 출력
    -1
    
  2. 예제 2

    입력
    2
    
    예상 출력
    2937