Sum Equals Xor

题目描述

你被给定一个以二进制表示的正整数 $L$。 有多少对非负整数 $(a, b)$ 满足下列条件？

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

由于此类配对的数量可能非常多，请将计数对 $10^9 + 7$ 取模后输出。

什么是 XOR？

整数 $A$ 与 $B$ 的 XOR，$A \text{ XOR } B$，定义如下：

当 $A \text{ XOR } B$ 用二进制表示时，$2^k$ 位上的数字（$k \geq 0$）为 $1$ 当且仅当 $A$ 或 $B$（但不是两者）在 $2^k$ 位上为 $1$，否则为 $0$。

例如，$3 \text{ XOR } 5 = 6$。（用二进制表示：$011 \text{ XOR } 101 = 110$。）

输入格式

输入按下列格式从标准输入给出： $L$

输出格式

打印满足条件的 $(a, b)$ 对的数量，对 $10^9 + 7$ 取模。

10

5

1111111111111111111

162261460

提示

$L$ 以二进制给出，且没有前导零。 1 \leq L < 2^{100\ 001}有五对 $(a, b)$ 满足条件：$(0, 0), (0, 1), (1, 0), (0, 2)$ 和 $(2, 0)$。

标签: AtCoder|abc129E

来源

AtCoder|abc129E