시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 132 50 42 57.534%

문제

희현이는 인터넷 ID를 만들 때 주로 쓰는 비밀번호가 있다. 하지만 이 비밀번호는 너무 길어서 희현이는 항상 쪽지에 적어 다니면서 확인을 한다. 하지만 장난꾸러기 영훈이는 이 쪽지를 가져가 1들 중 몇 개를 6로, 6들 중 몇 개를 1로 바꾸고 2들 중 몇 개를 7로 7들 중 몇 개를 2으로 바꾸는 장난을 쳤다. 따라서 영훈이가 장난쳐놓은 비밀번호 무용지물이 되었다. 왜냐하면 1이라고 쓰여 있어도 1 또는 6일수가 있고, 또한 6이라 쓰여 있어도 1 또는 6일수가 있다. 2과 7에서도 마찬가지이다. 하지만 희현이는 이러한 상황에 대비하여 비밀번호에 대한 한 가지 단서를 만들어 놓았는데 이는 다음과 같다.

비밀번호 수열의 숫자 중 1과 6을 모두 1로, 2와 7을 모두 2으로 바꾼 숫자와 1과 6을 모두 6으로 2과 7을 모두 7로 바꾼 숫자 사이에 가능한 경우를 모두 사전순으로 나열한 다음 그 중 k번째가 비밀번호이다.

따라서 이 단서를 통해 멘붕에 빠진 희현이를 도와 비밀번호를 다시 찾아보자.

입력

첫째 줄에 영훈이가 장난을 쳐서 바뀐 비밀번호가 주어진다. (비밀번호의 길이는 60자까지이고 첫 숫자가 0일수도 있다.)

둘째 줄에 숫자 k가 주어진다. (k ≤ 263 – 1)

출력

첫째 줄에 원래 비밀번호를 출력한다.

만약 k번째 비밀번호가 존재하지 않으면 -1을 출력한다.

예제 입력

1234567890
4

예제 출력

1234567890

힌트

1234567890

  • k = 1 : 1234512890
  • k = 2 : 1234517890
  • k = 3 : 1234562890
  • k = 4 : 1234567890