Binary Sum

You want to add up every natural number whose binary representation has at most $k$ digits.

A natural number is included in the sum when, written in binary, it has $k$ or fewer digits. In other words, you add every natural number from $1$ up to the largest number that fits in $k$ binary digits.

Given an integer $k$, write a program that prints this sum in binary.

The first line contains an integer $k$. ($1 \le k \le 10^6$)

On the first line, print in binary the sum of every natural number whose binary representation has at most $k$ digits.

For example, when $k = 3$ the natural numbers with at most $3$ binary digits are $1$ through $7$. Their sum is $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$, which in binary is $11100$.