E - 和等于异或

得分：$500$ 分

问题描述

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

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

由于满足条件的对数可能非常多，输出答案模 $10^9 + 7$。

两个整数 $A$ 和 $B$ 的异或运算 $A \text{ XOR } B$ 定义如下：

• 当二进制形式的 $A$ 和 $B$ 进行异或运算时，每一位的值由以下规则确定：如果 $A$ 和 $B$ 同时在该位上是 $1$ 或同时是 $0$，结果为 $0$；如果 $A$ 和 $B$ 在该位上只有一个是 $1$，结果为 $1$。

例如，$3 \text{ XOR } 5 = 6$。（换算成二进制：$011 \text{ XOR } 101 = 110$。）

</details>

约束条件

• $L$ 使用二进制表示，没有前导零。
• $1 \leq L < 2^{100\ 001}$

输入

从标准输入读入数据，输入格式如下：

$L$

输出

输出满足条件的对数 $(a, b)$ 的个数，结果模 $10^9 + 7$。

10

5

满足条件的五个对数是：$(0, 0), (0, 1), (1, 0), (0, 2)$ 和 $(2, 0)$。

1111111111111111111

162261460