和等于异或

题目描述

给定用二进制表示的正整数 $L$。

求满足以下条件的非负整数对 $(a, b)$ 有多少个:

• $a + b \le L$
• $a + b = a \text{ XOR } b$

不过,这个值可能非常大,请输出它除以 $10^9 + 7$ 的余数。

关于 XOR:

整数 $A, B$ 的按位异或 $A \text{ XOR } B$ 定义如下。

把 $A \text{ XOR } B$ 写成二进制时,$2^k$($k \ge 0$)位上的数字是:当 $A, B$ 写成二进制时 $2^k$ 位上的数字中只有一个是 $1$ 时为 $1$,否则为 $0$。

例如,$3 \text{ XOR } 5 = 6$(写成二进制为:$011 \text{ XOR } 101 = 110$)。

输入格式

输入按以下格式从标准输入给出:

$L$

输出格式

输出满足条件的对 $(a, b)$ 的数量除以 $10^9 + 7$ 的余数。

样例

10

5

满足条件的 $(a, b)$ 有 $(0, 0), (0, 1), (1, 0), (0, 2), (2, 0)$ 共 $5$ 个。

1111111111111111111

162261460

数据范围

• $L$ 用二进制表示给出,首位字符必定是 $1$
• $1 \le L \lt 2^{100,001}$