Là một người âm thầm đam mê máy tính, Farmer John gắn cho tất cả bò của mình các số nhị phân. Tuy nhiên, ông hơi mê tín và chỉ gắn cho bò những số nhị phân có đúng \(K\) bit 1 (\(1 \le K \le 10\)). Tất nhiên, bit đầu của mỗi nhãn luôn là bit 1. FJ gán nhãn theo thứ tự giá trị tăng dần, bắt đầu từ nhãn hợp lệ nhỏ nhất có thể — một số gồm \(K\) bit, tất cả đều là 1. Đáng tiếc, ông không còn nhớ mình đã gán nhãn đến đâu và cần bạn giúp: hãy xác định nhãn thứ \(N\) mà ông cần gán (\(1 \le N \le 10^7\)).

Dữ liệu vào

Dòng 1 chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách.

Dữ liệu ra

In nhãn thứ \(N\) mà FJ cần gán.

Ví dụ

7 3

10110

Nguồn

USACO 2012 February Contest, Silver - Cow IDs: https://usaco.org/index.php?page=viewproblem2&cpid=116

Tác giả: Brian Dean, 2012.