问题描述

如果一个整数的二进制表示是连续若干个 “$1$” 后紧跟着连续若干个 “$0$” ，我们将这类数称为 “趣味二进制” 数 。例如，十进制数 $12$ 的二进制表示为 $1100$， $16$ 的二进制表示为 $10000$ ，它们都是 趣味二进制数 。但 $7$ 的二进制表示只含连续 $1$ 但不含 $0$ 就不属于 “趣味二进制” 数。

在十进制数 $1,2, ...,n$ 之间，有多少个这样的趣味二进制数呢？

输入格式

输入一行，一个正整数 $n$。

输出格式

输出一行，一个整数 ，表示趣味二进制数的个数。

样例

12

5

$1,2,...,12$ 中的趣味二进制数分别是 $2,4,6,8,12$。

16384

92

数据范围

• 对于 $100\%$ 的数据，有 $1 ≤ n ≤ 1, 000, 000, 000$。