問題文

正整数 $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$は二進数表記で与えられ、先頭文字は必ず $1$ である
• $1 \\leq L < 2^{100,001}$

入力

入力は以下の形式で標準入力から与えられる。

$L$

出力

条件を満たす組 $(a, b)$ の個数を $10^9 + 7$ で割った余りを出力せよ。

入力例 1

10

出力例 1

5

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

入力例 2

1111111111111111111

出力例 2

162261460