You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

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

在⼗进制数 $1, 2, … , n$ 之间 ，有多少个这样的趣味⼆进制数呢？

输入格式

输⼊⼀⾏ ，⼀个正整数 $n$。

输出格式

输出⼀⾏ ，⼀个整数 ，表⽰趣味⼆进制数的个数。

样例

12

5

提示

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