AT_abc129_e [ABC129E] Sum Equals Xor

题目描述

给定一个正整数 $L$，以二进制形式表示。请计算满足以下条件的非负整数对 $(a, b)$ 的个数：

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

由于答案可能非常大，请输出对 $10^9 + 7$ 取模的结果。

XOR 的定义如下：

对于整数 $A, B$，它们的按位异或 $a\ \text{XOR}\ b$ 定义为：

将 $a\ \text{XOR}\ b$ 用二进制表示时，第 $2^k$ 位（$k \geq 0$）的值为：如果 $A, B$ 的二进制表示中第 $2^k$ 位只有一个为 $1$，则该位为 $1$，否则为 $0$。例如，$3\ \text{XOR}\ 5 = 6$（二进制为：$011\ \text{XOR}\ 101 = 110$）。

输入格式

输入以以下格式从标准输入读入。

$L$

输出格式

请输出满足条件的 $(a, b)$ 组数，对 $10^9 + 7$ 取模。

样例 1

输入

10

输出

5

样例 2

输入

1111111111111111111

输出

162261460

说明/提示

限制

• $L$ 以二进制形式给出，首位一定是 $1$
• $1 \leq L < 2^{100001}$

样例解释 1

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

由 ChatGPT 4.1 翻译