Algorithms and Data Structures

• Status

• # Binary Representation of Numbers

We have been working with integers for quite a while. But how are they actually represented in our computers? We know that everything on our machines is either 0 or 1. So, all the integers are represented in some form that is stored as a sequence of 0s and 1s. We call that the binary representation of numbers.
Any number can be represented as a sum of powers of 2 (1, 2, 4, 8, 16, 32, …):
• 19 = 16 + 2 + 1
• 20 = 16 + 4
• 140 = 128 + 8 + 4
Therefore, we can create a sequence of 0s and 1s that would represent the powers of 2, and to get the final number, we would just add those up together. In case the representation contains 1 - we include the corresponding power of 2, and in case it’s a 0 - we exclude it. For 140 we included the 128, 8, and 4 powers of 2 while excluding 64, 32, 16, 2, and 1. We can do that for any number:
 Power of 2 Power of 2 in decimal 512 256 128 64 32 16 8 4 2 1 Binary (include/exclude) 0 1 0 0 1 1 0 1 1 1 Sum (311) 311 311 55 55 55 23 7 7 3 1
The convention is to write the small powers of 2 on the right, and progress to larger ones as we move to the left. So, we first start from 1, then process 2, then 4, etc.
Starting from the rightmost power of 2 we sum up all the powers of 2 that have a 1 in the binary representation and obtain the final number.

### Challenge

Given a binary representation, you are asked to write a program to print the original number.

#### Input

The only line of the input contains the string `s` of 0s and 1s (1 ≤ |s| ≤ 31).

#### Output

The program should print the actual number.

#### Examples

 Input Output 0100110111 311 101 5 110 6 111 7