Migrated from Lutece 548 Cow IDs

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Being a secret computer geek, Farmer John labels all of his cows with binary numbers. However, he is a bit superstitious, and only labels cows with binary numbers that have exactly $K$ 1 bits ($1 \leq K \leq 10$). The leading bit of each label is always a 1 bit, of course. FJ assigns labels in increasing numeric order, starting from the smallest possible valid label -- a $K$-bit number consisting of all 1 bits. Unfortunately, he loses track of his labeling and needs your help: please determine the $N_{th}$ label he should assign ($1 \leq N \leq 10^7$).

Input

• Line $1$: Two space-separated integers, $N$ and $K$.

Output

• Line $1$: Output the $N_{th}$ label he should assign

Samples

7 3

10110

Resources

USACO Feb 2012