题目描述

You are given a positive integer $L$ in base two. How many pairs of non-negative integers $(a, b)$ satisfy the following conditions?

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

Since there can be extremely many such pairs, print the count mod $10^9 + 7$.

What is XOR?

The XOR of integers $A$ and $B$, $A \text{ XOR } B$, is defined as follows:

• When $A \text{ XOR } B$ is written in base two, the digit in the $2^k$'s place ($k \geq 0$) is $1$ if either $A$ or $B$, but not both, has $1$ in the $2^k$'s place, and $0$ otherwise.

For example, $3 \text{ XOR } 5 = 6$. (In base two: $011 \text{ XOR } 101 = 110$.)

给你一个以二为底的正整数 $L$ 。有多少对非负整数 $(a, b)$ 满足下列条件？

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

由于这样的整数对可能极多，请打印以 $10^9 + 7$ 为模数的计数。

什么是 XOR？

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

• 当以二进制写入 $A \text{ XOR } B$ 时，如果 $A$ 或 $B$ 中的任何一个（而不是两个）在 $2^k$ 的位置上有 $1$ ，则 $2^k$ 的位置（ $k \geq 0$ ）上的数字是 $1$ ，否则是 $0$ 。

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

输入格式

输入内容按以下格式标准输入：

$L$

输出格式

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

样例 #1

样例输入 #1

10

样例输出 #1

5

样例 #2

样例输入 #2

1111111111111111111

样例输出 #2

162261460

说明

数据规模与约定

• $L$ 以二进制表示，不含前导零。
• $1 \leq L \lt 2^{100\ 001}$

样例 $1$ 解释

有五对 $(a, b)$ 符合条件： $(0, 0), (0, 1), (1, 0), (0, 2)$ 和 $(2, 0)$ .