Cho tập hợp tất cả các xâu nhị phân có độ dài N được sắp xếp theo thứ tự từ điển. Ví dụ N = 3 ta có tập hợp: 000, 001, 010, 011, 100, 101, 110, 111.

Trong tập hợp trên, ta có:

• Xâu nhị phân 100: ở vị trí số 5.
• Vị trí số 7 trong tập là xâu nhị phân: 110.

Yêu cầu: Với một số N (N <= 63) cho trước, hãy cho biết:

• Xâu nhị phân S (có độ dài N) nằm ở vị trí nào của tập.
• Vị trí thứ K (1 <= K <= 10¹⁸) là xâu nhị phân nào?

Dữ liệu vào: Cho trong file NHIPHAN.INP:

• Dòng đầu chứa một số nguyên N, là độ dài của các xâu nhị phân.
• Dòng thứ hai chứa một xâu nhị phân S có độ dài bằng N.
• Dòng thứ ba chứa một số nguyên K.

Dữ liệu ra: In ra file NHIPHAN.OUT:

• Dòng đầu tiên chứa một số nguyên là vị trí của S trong tập hợp.
• Dòng thứ hai ghi xâu nhị phân có N phần tử nằm ở vị trí thứ K.