题目描述

求从 $0$ 到 $n - 1$ 中整数 $\operatorname{popcount}$ 值的异或和。

其中 $\operatorname{popcount}(x)$ 表示 $x$ 在二进制下 $1$ 的个数。

输入格式

一行一个无前导零的二进制整数 $n$。

输出格式

一行一个整数表示异或和。

110

1

1011101011

13

1010100101110101111010100010101010101011110101010

37

数据范围与提示

共 $20$ 个测试点，每个测试点 $5$ 分。

设 $k$ 为输入串的长度。
对于所有数据，$1\le k \le 2^{24}$。