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} \times 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.}~

Input

• Một số nguyên dương duy nhất là ~n~ ~(1 \leq n \leq 10^{9})~.

Output

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

Sample Input

7

Sample Output

46