Informatica Online Judge

  Cow IDs [0922 / 039A]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 21   Total Tried : 161


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[USACO (Brian Dean, 2012)]

Background

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 <= K <= 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 Nth label he should assign (1 <= N <= 10^7).

Input

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

Output

* Line 1 : Output the answer.

IO Example

Input
7 3

Output
10110

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]