아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

호반우가 학교에 지각한 이유 2

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

요약
앞 두 자리가 A, 뒤 두 자리가 B이며 모든 연속한 두 자릿수가 소수인 N자리 수를 아무거나 하나 찾는다.
난이도

보통10점 중 6점

유형
그래프, DFS, 백트래킹, 수학
정답자
아직 제출이 없습니다

문제

이세계를 모험할 때는 무기가 필요한 법이기에 호반우는 현재 신에게 받은 소수소수검의 사용법을 익히고 있다.

소수소수검을 사용하기 위해서는 검이 제시하는 두 자릿수의 소수 A,,BA,\\,B와 양의 정수 NN을 이용해 소수소수를 만들어야 한다. 소수소수란 해당 수 자체가 소수일 필요는 없지만 모든 연속된 두 자릿수가 소수인 수를 말한다.

예를 들어 973973은 9797과 7373이 소수이므로 소수소수가 되지만, 937937은 9393이 소수가 아니기에 소수소수가 아니다.

이때 소수소수를 만들 때 한가지 제한사항이 있는데 처음 두 자릿수는 AA이고 마지막 두 자릿수는 BB인 NN 자릿수의 소수소수를 만들어야 한다.

아직 검의 사용법에 익숙하지 않은 호반우를 도와 소수소수를 만들어 주자.

입력

첫 번째 줄에 소수 A,,BA,\\,B와 양의 정수 NN이 공백을 두고 주어진다. (7≤N≤100,,11≤A,,B≤97)(7 \le N \le 100,\\,11 \le A,\\,B \le 97)

출력

주어진 수들로 소수소수를 만들 수 있다면 소수소수를 아무거나 하나 출력하고 만들 수 없다면 -1을 출력한다.

힌트

소수란 22 이상의 정수 중에서 11과 자기 자신으로만 나누어떨어지는 수이다.

예제2

  1. 예제 1

    입력
    47 37 7
    
    예상 출력
    4719737
    
  2. 예제 2

    입력
    17 23 10
    
    예상 출력
    -1