#P0894. 黑白号码牌

黑白号码牌

题目描述

训练营要给一批储物柜贴号码牌。

普通号码牌可以使用 09 中的任意数字,但这次老师准备了一套特别的黑白号码牌:每一位上只能出现数字 0 或数字 1

例如:

  • 1 是合法的黑白号码;
  • 1011101 也是合法的黑白号码;
  • 12201023 都不是合法的黑白号码。

注意,号码不能有前导零,所以 001001 都不作为要统计的号码。

现在给定一个整数 N,请你统计从 1N 之间,一共有多少个合法的黑白号码。

输入格式

输入一行,一个整数 N

输出格式

输出一个整数,表示 1N 之间合法黑白号码的个数。

样例 1

10
2

样例 2

11
3

样例说明

110 中,合法黑白号码为 110,所以样例 1 的答案为 2
111 中,合法黑白号码为 11011,所以样例 2 的答案为 3

数据范围

  • 1<=N<=10181 <= N <= 10^{18}