题目描述

正整数 $L$ が二進数表記で与えられます。 以下の条件を満たす非負整数 $a,\ b$ の組 $(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$ で割った余りを出力せよ。

题目大意

以二进制形式给出一个整数 $L$ ，问有多少个非负整数对 $(a, b)$ 满足：$a+b = a \oplus b \le L$。答案对 $10^9 + 7$ 取模。

10

5

1111111111111111111

162261460

提示

制約

• $L$は二進数表記で与えられ、先頭文字は必ず $1$ である
• $1\ \leq\ L\ <\ 2^{100,001}$

Sample Explanation 1

条件を満たす $(a,\ b)$ としては $(0,\ 0),\ (0,\ 1),\ (1,\ 0),\ (0,\ 2),\ (2,\ 0)$ の $5$ つが考えられます。