모빌 이진수

0과 1이 적힌 추와 여러 가로 막대로 이루어진 모빌이 있다. 각 가로 막대 아래에는 왼쪽부터 차례대로 0, 1, 또는 다른 가로 막대가 매달려 있다.

모빌은 항상 균형이 잡혀 있다고 가정한다. 바람이 불면 어떤 가로 막대든 회전할 수 있고, 그 막대 아래에 매달린 것들의 좌우 순서가 뒤집힌다. 여러 막대를 독립적으로 회전시키면 하나의 모빌에서 여러 상태가 만들어진다.

하나의 상태는 다음 규칙으로 표현한다. 가로 막대 하나를 괄호 한 쌍으로 나타내고, 그 괄호 안에 그 막대 아래의 0, 1, 하위 가로 막대 표현을 현재 왼쪽에서 오른쪽 순서대로 적는다. 전체 표현은 항상 여는 괄호로 시작해 닫는 괄호로 끝난다.

현재 상태가 (10(1011)00(10(01)))라면 괄호를 지우고 왼쪽부터 0과 1을 읽어 얻는 이진수는 101011001001이다. 이 상태에서 가운데의 (1011) 막대가 회전하면 101101001001을 얻을 수 있고, 이어서 가장 위 막대가 회전하면 전체 순서가 뒤집혀 100100101101을 얻을 수 있다.

이처럼 주어진 모빌의 어떤 상태에서 만들 수 있는 이진수를 모빌 이진수라고 하자. 서로 다른 회전 상태가 같은 이진수를 만들 수 있으므로, 같은 이진수는 한 번만 센다.

다음 모빌 (0(1(01))1)에서는 아래와 같은 과정이 가능하다.

• (0((01)1)1) -> 00111 -> 가장 작은 수
• (0((10)1)1) -> 01011 -> 두 번째로 작은 수
• (0(1(01))1) -> 01011 -> 위와 같은 수
• (0(1(10))1) -> 01101 -> 세 번째로 작은 수

관찰 가능한 서로 다른 모빌 이진수들을 사전순, 즉 같은 길이의 이진수에 대한 크기순으로 정렬했을 때 K번째 수를 구하라. K가 서로 다른 모빌 이진수의 개수보다 크면 NO를 출력한다.

첫째 줄에 0, 1, 괄호로 이루어진 모빌의 상태 표현이 공백 없이 주어진다. 표현에 포함된 0, 1, 괄호의 전체 개수는 200개 이하이다. 둘째 줄에 자연수 K가 주어지며, K는 1 이상 1,000 이하이다. 입력은 항상 올바른 형식이다.

한 줄에 K번째로 작은 모빌 이진수를 출력한다. 그런 수가 없으면 NO를 출력한다. 정답이 0으로 시작하면 앞의 0도 그대로 출력해야 한다.