题目描述

• 所谓 01 串，就是只含有 0 与 1 的字符串；
• 所谓 $n$ 位 01 串，就是长度为 $n$ 的 01 串；
• 所谓全体 $n$ 位 01 串，就是所有长度为 $n$ 的 01 串构成的总集，共有 $2^n$ 个 $n$ 位 01 串。

格雷序列是一种排列全体 $n$ 位 01 串的方法。它满足：

• 所有 $n$ 位 01 串在序列中不重复不遗漏；
• 在序列中相邻的 01 串，有且只有一位比特不同；
• 第一个 01 串与最后一个 01 串有且只有一位比特不同。

格雷序列的构造方法，是递归进行的：

• $1$ 位格雷序列如下： 0, 1。
• 当 $k> 0$ 时，$k+1$ 位格雷序列构造方案如下：
  • 首先，构造一个 $k$ 位格雷码序列，在每个串前增加一个 0， 构成 $k+1$ 位格雷码序列的前半部分；
  • 其次，再构造一个 $k$ 位格雷序列，将这个序列倒转（首项成末项，末项变成首项），然后在每个串前加一个 1，构成 $k+1$ 位格雷序列的后半部分；

可以验证上述构造的序列满足所有要求，验证过程略。按该方法，$2$ 位格雷序列的构造过程是：

• 已知 $1$ 位格雷序列为 0, 1
• 则前两个格雷码为 00, 01
• 已知 $1$ 位格雷序列的倒转为 1, 0
• 则后两个格雷码为 11, 10
• 合并得到 00, 01, 11, 10。

$3$ 位格雷序列可以这样推出：

• 已知 2 位格雷序列为：00, 01, 11, 10。
• 则前四个：000, 001, 011, 010。
• 已知 $2$ 位格雷序列的倒转为 10, 11, 01, 00。
• 则后四个：110, 111, 101, 100。
• 合并得：000, 001, 011, 010, 110, 111, 101, 100

对每个 01 串，它在格雷序列中出现的位置就是这个 01 串的编号，编号应该从 $0$ 开始计数。

给定一个 01 串，请求出这个 01 串在格雷序列中的编号。

输入格式

• 单个 01 串

输出格式

10

3

111

5

数据范围

设 $|S|$ 表示输入的长度

• $30\%$ 的数据，$1 \le |S| \le 10$
• $50\%$ 的数据，$1 \le |S| \le 30$
• $100\%$ 的数据，$1 \le |S| \le 64$