Giải bài trực tuyến

Cho dãy số F dài vô tận. Nguyên tắc xây dựng dãy F rất đơn giản.

• F[1] = 1
• Với i > 1, đầu tiên ta lấy F[i] = F[i - 1] * 2, sau đó sắp xếp các chữ số trong F[i] theo thứ tự tăng dần. (Các chữ số 0 ở đầu F[i], ta coi như là không có nghĩa và có thể xóa đi).

Như vậy, các số đầu tiên trong dãy số F là:

1, 2, 4, 8, 16, 23, 46, 29, 58, ...

Cho số n, bạn hãy tìm số F[n]. Biết rằng số lượng chữ số của F[n] luôn nhỏ hơn 10^6.

Dữ liệu

• Một số nguyên dương duy nhất là n (1 ≤ n ≤ 10⁹).

Kết quả

• Một số nguyên dương duy nhất là số cần tìm.

Ví dụ

Input:
7

Output:
46