Cow IDs

Interview

Time limit1sMemory limit128 MB

Summary

Find the N-th smallest binary number that has exactly K one-bits and no leading zeros, then print it in binary.

Level: Medium5 of 10
Topics: Combinatorics, Math, Bit manipulation, Implementation
Solved: No attempts yet

Problem

Farmer John, a secret computer geek, labels every one of his cows with a binary number. Being a little superstitious, he only uses binary numbers that contain exactly $K$ one-bits ( $1 \le K \le 10$ ). As with any binary number, the most significant bit of a label is always $1$ (there are no leading zeros).

Farmer John hands out labels in increasing numeric order, beginning with the smallest valid label — the $K$ -bit number whose bits are all $1$ . He has lost track of his numbering and needs your help: determine the $N$ -th label he assigns ( $1 \le N \le 10^7$ ).

Input

One line containing two space-separated integers $N$ and $K$ .

Output

Output a single line containing the $N$ -th label written in binary — a string of the characters 0 and 1 with no leading zeros.

Note

Listing the binary numbers with exactly three $1$ -bits in increasing order gives $111, 1011, 1101, 1110, 10011, 10101, 10110, \dots$ The $7$ -th of these is $10110$ .

Examples6

Example 1
Input
```
7 3
```
Expected output
```
10110
```
Example 2
Input
```
1 1
```
Expected output
```
1
```
Example 3
Input
```
1 3
```
Expected output
```
111
```
Example 4
Input
```
1 10
```
Expected output
```
1111111111
```
Example 5
Input
```
4 3
```
Expected output
```
1110
```
Example 6
Input
```
5 2
```
Expected output
```
1010
```