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.

TODO: Embed link to experiment

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).