A sequence of coin toss can be encoded as a binary string, ’0’ for head, ’1’ for tail. Given an encoded sequence \(S\),
toss the coin until \(S\) appears in the result sequence then stop.
Let \(T\) be the number of coin toss taken for \(S\) to appear, find the expected value of \(T\).

Input

Let \(T\) be the number of coin toss taken for \(S\) to appear, find the expected value of \(T\).

Output

Let \(T\) be the number of coin toss taken for \(S\) to appear, find the expected value of \(T\).

Example

1
00

6