题目描述

给定一个二进制表示的正整数 $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$，而另一个不为 $1$，否则为 $0$。

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

约束条件

• $L$ 的二进制表示中不包含前导零。
• $1 \\leq L < 2^{100\\ 001}$

输入

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

$L$

输出

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

示例输入1

10

示例输出1

5

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

示例输入2

1111111111111111111

示例输出2

162261460